50902023-04-16 16:01:33szilMultiplikátoros telebabrátorcpp14Wrong answer 0/100333ms129148 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] = {nullptr, nullptr};
    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 >= 0) a[bit]->add(i-1, n, v);
        else u = v;
    }

    int qry(int i, int n) {
        if (i == -1) return u;
        int bit = (n >> i) & 1;
        if (a[!bit] != nullptr) {
            return a[!bit]->qry(i-1, n);
        } else {
            assert(a[bit] != nullptr);
            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
2Accepted8ms9800 KiB
subtask20/20
3Wrong answer8ms10012 KiB
4Accepted8ms10216 KiB
5Wrong answer8ms10316 KiB
6Accepted8ms10364 KiB
7Wrong answer8ms10612 KiB
8Wrong answer8ms10488 KiB
9Accepted8ms10488 KiB
10Accepted8ms10484 KiB
11Accepted8ms10760 KiB
12Wrong answer8ms11044 KiB
13Accepted8ms11216 KiB
14Wrong answer8ms11252 KiB
15Wrong answer8ms11140 KiB
16Wrong answer8ms11124 KiB
subtask30/80
17Wrong answer257ms113664 KiB
18Accepted256ms113684 KiB
19Wrong answer259ms113640 KiB
20Accepted321ms113864 KiB
21Accepted259ms113852 KiB
22Wrong answer263ms113836 KiB
23Accepted261ms113872 KiB
24Accepted259ms113852 KiB
25Wrong answer319ms113772 KiB
26Wrong answer316ms114188 KiB
27Accepted286ms114204 KiB
28Accepted314ms114276 KiB
29Wrong answer289ms113796 KiB
30Wrong answer321ms114060 KiB
31Accepted323ms114608 KiB
32Accepted289ms117384 KiB
33Accepted333ms120460 KiB
34Accepted333ms129148 KiB
35Wrong answer310ms115604 KiB
36Accepted246ms115448 KiB
37Accepted301ms115144 KiB
38Accepted252ms115020 KiB
39Wrong answer298ms114884 KiB
40Wrong answer289ms114008 KiB