5089 2023. 04. 16 15:57:08 szil Multiplikátoros telebabrátor cpp14 Hibás válasz 0/100 321ms 162144 KiB
#include <bits/stdc++.h>

using ll = long long;
using namespace std;

const int MAXN = 100001;

vector<pair<int, int>> g[MAXN];
int d[MAXN];

struct Node {
    Node *a[2];
    int u = -1;

    void add(int i, int n, int v) {
        int bit = (n >> i) & 1;
        if (a[bit] == nullptr) {
            a[bit] = new Node();
        }
        if (i) a[bit]->add(i-1, n, v);
        else u = v;
    }

    int qry(int i, int n) {
        if (i == 0) return u;
        int bit = (n >> i) & 1;
        if (a[!bit] != nullptr) {
            return a[!bit]->qry(i-1, n);
        } else {
            return a[bit]->qry(i-1, n);
        }
    }
};

Node *root;

void dfs(int u, int p = 0) {
    for (auto [v, w] : g[u]) {
        if (v != p) {
            d[v] = d[u] ^ w;
            root->add(31, d[v], v);
            dfs(v, u);
        }
    }
}

void solve() {
    root = new Node();
    int n; cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int a, b, w; cin >> a >> b >> w;
        g[a].push_back({b, w});
        g[b].push_back({a, w});
    }
    dfs(1);
    for (int i = 1; i <= n; i++) {
        cout << root->qry(31, d[i]) << " ";
    }
    cout << "\n";
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    solve();
    return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 4ms 6672 KiB
2 Elfogadva 8ms 9728 KiB
subtask2 0/20
3 Hibás válasz 8ms 9984 KiB
4 Elfogadva 8ms 10248 KiB
5 Hibás válasz 8ms 10404 KiB
6 Elfogadva 8ms 10644 KiB
7 Hibás válasz 8ms 10812 KiB
8 Hibás válasz 8ms 11084 KiB
9 Elfogadva 8ms 11436 KiB
10 Elfogadva 8ms 11444 KiB
11 Elfogadva 8ms 11664 KiB
12 Hibás válasz 8ms 11944 KiB
13 Elfogadva 8ms 12420 KiB
14 Hibás válasz 8ms 12132 KiB
15 Hibás válasz 8ms 12168 KiB
16 Hibás válasz 8ms 12340 KiB
subtask3 0/80
17 Hibás válasz 252ms 110756 KiB
18 Hibás válasz 250ms 112856 KiB
19 Hibás válasz 250ms 115124 KiB
20 Hibás válasz 305ms 117504 KiB
21 Elfogadva 256ms 119660 KiB
22 Hibás válasz 307ms 121720 KiB
23 Hibás válasz 305ms 123868 KiB
24 Elfogadva 252ms 126220 KiB
25 Hibás válasz 254ms 128176 KiB
26 Hibás válasz 305ms 130624 KiB
27 Elfogadva 308ms 132972 KiB
28 Hibás válasz 252ms 135160 KiB
29 Hibás válasz 316ms 136680 KiB
30 Hibás válasz 312ms 138836 KiB
31 Hibás válasz 314ms 141348 KiB
32 Elfogadva 261ms 146220 KiB
33 Hibás válasz 321ms 151432 KiB
34 Hibás válasz 319ms 162144 KiB
35 Hibás válasz 247ms 150772 KiB
36 Hibás válasz 234ms 152696 KiB
37 Hibás válasz 238ms 154568 KiB
38 Elfogadva 236ms 156640 KiB
39 Hibás válasz 232ms 158508 KiB
40 Hibás válasz 248ms 160016 KiB