50892023-04-16 15:57:08szilMultiplikátoros telebabrátorcpp14Wrong answer 0/100321ms162144 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;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted4ms6672 KiB
2Accepted8ms9728 KiB
subtask20/20
3Wrong answer8ms9984 KiB
4Accepted8ms10248 KiB
5Wrong answer8ms10404 KiB
6Accepted8ms10644 KiB
7Wrong answer8ms10812 KiB
8Wrong answer8ms11084 KiB
9Accepted8ms11436 KiB
10Accepted8ms11444 KiB
11Accepted8ms11664 KiB
12Wrong answer8ms11944 KiB
13Accepted8ms12420 KiB
14Wrong answer8ms12132 KiB
15Wrong answer8ms12168 KiB
16Wrong answer8ms12340 KiB
subtask30/80
17Wrong answer252ms110756 KiB
18Wrong answer250ms112856 KiB
19Wrong answer250ms115124 KiB
20Wrong answer305ms117504 KiB
21Accepted256ms119660 KiB
22Wrong answer307ms121720 KiB
23Wrong answer305ms123868 KiB
24Accepted252ms126220 KiB
25Wrong answer254ms128176 KiB
26Wrong answer305ms130624 KiB
27Accepted308ms132972 KiB
28Wrong answer252ms135160 KiB
29Wrong answer316ms136680 KiB
30Wrong answer312ms138836 KiB
31Wrong answer314ms141348 KiB
32Accepted261ms146220 KiB
33Wrong answer321ms151432 KiB
34Wrong answer319ms162144 KiB
35Wrong answer247ms150772 KiB
36Wrong answer234ms152696 KiB
37Wrong answer238ms154568 KiB
38Accepted236ms156640 KiB
39Wrong answer232ms158508 KiB
40Wrong answer248ms160016 KiB