Submission #5463492


Source Code Expand

Copy
#if 1
#pragma GCC optimize "O3"
#include <array>
#include <bitset>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <functional>
#include <string>
#include <fstream>
#include <iostream>
#include <sstream>
#include <random>
#include <cassert>
#include <cmath>
#include <cstring>
#include <chrono>
using namespace std;
using i8 = int8_t; using i16 = int16_t; using i32 = int32_t; using i64 = int64_t; using u8 = uint8_t; using u16 = uint16_t; using u32 = uint32_t; using u64 = uint64_t; using f32 = float; using f64 = double;
template <class T> inline T sq(T a) { return a * a; }
template <class T> inline bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } return false; }
template <class T> inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } return false; }
void _u() { cerr << endl; } template <class H, class... T> void _u(H&& h, T&&... t) { cerr << h << ", "; _u(move(t)...); }
#define _polyfill(v) v
#define _overload3(a, b, c, d, ...) d
#define _rep3(i, a, b) for (i32 i = i32(a); i < i32(b); ++i)
#define _rep2(i, b) _rep3(i, 0, b)
#define _rep1(i) for (i32 i = 0; ; ++i)
#define rep(...) _polyfill(_overload3(__VA_ARGS__, _rep3, _rep2, _rep1)(__VA_ARGS__))
#define A(a) begin(a), end(a)
#define S(a) i32((a).size())
#define U(...) { cerr << #__VA_ARGS__ << ": "; _u(__VA_ARGS__); }
#define lin U(__LINE__)
#define exi exit(0);
#endif

class timer {
    vector<timer> timers;
    int n = 0;
public:
    double limit = 2.95;
    double t = 0;
    timer() {}
    timer(int size) : timers(size) {}
    bool elapses() const {
        return time() - t > limit;
    }
    void measure() {
        t = time() - t;
        ++n;
    }
    void measure(char id) {
        timers[id].measure();
    }
    void print() {
        if (n % 2)
            measure();
        for (int i = 0; i < 128; ++i) {
            if (timers[i].n)
                cerr << (char)i << ' ' << timers[i].t << 's' << endl;
        }
        cerr << "  " << t << 's' << endl;
    }
    static double time() {
#ifdef LOCAL
        return __rdtsc() / 3.3e9;
#else
        using namespace std::chrono;
        return duration_cast<milliseconds>(system_clock::now().time_since_epoch()).count() / 1000.0;
#endif
    }
} timer(128);

constexpr bool Deterministic = 0;
class rando {
    unsigned y;
public:
    rando(unsigned y) : y(y) {}
    unsigned next() {
        return y ^= (y ^= (y ^= y << 13) >> 17) << 5;
    }
    int next(int b) {
        return next() % b;
    }
    int next(int a, int b) {
        return next(b - a) + a;
    }
    double nextDouble(double b = 1) {
        return b * next() / 4294967296.0;
    }
    double nextDouble(double a, double b) {
        return nextDouble(b - a) + a;
    }
    int operator() (int b) {
        return next(b);
    }
} rando(Deterministic ? 2463534242 : random_device()());

i32 c[100010];
vector<pair<i32, i32>> edges[100010];

i32 main() {
    i32 N;
    cin >> N;
    rep (_, N) {
        i32 u, v, w;
        cin >> u >> v >> w;
        --u;
        --v;
        edges[u].emplace_back(v, w);
        edges[v].emplace_back(u, w);
    }
    c[0] = -1;
    vector<i32> a = { 0 };
    rep (i, S(a)) {
        i32 j = a[i];
        for (auto& p : edges[j]) {
            i32 e = p.first;
            i32 w = p.second;
            if (c[e]) continue;
            c[e] = -c[j];
            a.emplace_back(e);
        }
    }
    rep (i, N) {
        cout << (c[i] > 0 ? 1 : 0) << endl;
    }
    return 0;
}

Submission Info

Submission Time
Task D - Even Relation
User hakomo
Language C++14 (GCC 5.4.1)
Score 0
Code Size 3713 Byte
Status

Test Cases

Set Name Score / Max Score Test Cases
All 0 / 400 sample_01, sample_02, testcase_01, testcase_02, testcase_03, testcase_04, testcase_05, testcase_06, testcase_07, testcase_08, testcase_09, testcase_10, testcase_11, testcase_12, testcase_13, testcase_14, testcase_15, testcase_16, testcase_17, testcase_18, testcase_19, testcase_20
Sample 0 / 0 sample_01, sample_02
Case Name Status Exec Time Memory
sample_01 3 ms 2560 KB
sample_02 3 ms 2560 KB
testcase_01 166 ms 6008 KB
testcase_02 107 ms 4856 KB
testcase_03 131 ms 5368 KB
testcase_04 153 ms 5120 KB
testcase_05 241 ms 6528 KB
testcase_06 102 ms 4352 KB
testcase_07 3 ms 2560 KB
testcase_08
testcase_09 3 ms 2560 KB
testcase_10 69 ms 4096 KB
testcase_11 7 ms 2688 KB
testcase_12 103 ms 4608 KB
testcase_13 107 ms 4608 KB
testcase_14 107 ms 4608 KB
testcase_15 264 ms 7292 KB
testcase_16 266 ms 7292 KB
testcase_17 252 ms 7164 KB
testcase_18 47 ms 3584 KB
testcase_19 183 ms 6016 KB
testcase_20 68 ms 3840 KB