Submission #6251009

---

Source Code Expand

// {{{
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
// }}}

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;

static constexpr int mod = (int)1e9 + 7;
static constexpr int inf = 100100100;
static constexpr ll linf = 1e18;
static constexpr double eps = 1e-9;
static constexpr double pi = 3.14159265359;

#define rep(i, n) for (ll i = 0; i < n; ++i)
#define rrep(i, n) for (ll i = n; i >= 0; --i)
#define all(c) begin(c), end(c)
#define rall(c) rbegin(c), rend(c)
#define pb push_back
#define ist insert
#define fst first
#define snd second


map<ll, vector<pair<ll, ll>>> G;
map<ll, ll> C;


int main() {
    // cin.tie(0);
    // ios_base::sync_with_stdio(false);
    ll N;
    cin >> N;
    for (ll i = 1; i <= N; ++i) {
        G[i];
        C[i] = -1;
    }
    rep (i, N - 1) {
        ll u, v, w;
        cin >> u >> v >> w;
        G[u].pb({v, w});
        G[v].pb({u, w});
    }
    set<ll> memo;
    queue<pair<ll, ll>> q;
    q.push({1, 0});
    for (ll i = 1; i <= N; ++i) {
        auto u = q.front();
        //cout << u.fst << ", " << u.snd << endl;
        q.pop();
        if (u.snd % 2 == 0) {
            C[u.fst] = 1;
        } else {
            C[u.fst] = 0;
        }
        memo.ist(u.fst);
        for (auto v : G[u.fst]) {
            if (memo.count(v.fst)) continue;
            q.push({v.fst, u.snd + v.snd});
        }
    }
    for (ll i = 1; i <= N; ++i) {
        cout << C[i] << endl;
    }
}

Submission Info

Judge Result