5090 2023. 04. 16 16:01:33 szil Multiplikátoros telebabrátor cpp14 Hibás válasz 0/100 333ms 129148 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;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 4ms 6672 KiB
2 Elfogadva 8ms 9800 KiB
subtask2 0/20
3 Hibás válasz 8ms 10012 KiB
4 Elfogadva 8ms 10216 KiB
5 Hibás válasz 8ms 10316 KiB
6 Elfogadva 8ms 10364 KiB
7 Hibás válasz 8ms 10612 KiB
8 Hibás válasz 8ms 10488 KiB
9 Elfogadva 8ms 10488 KiB
10 Elfogadva 8ms 10484 KiB
11 Elfogadva 8ms 10760 KiB
12 Hibás válasz 8ms 11044 KiB
13 Elfogadva 8ms 11216 KiB
14 Hibás válasz 8ms 11252 KiB
15 Hibás válasz 8ms 11140 KiB
16 Hibás válasz 8ms 11124 KiB
subtask3 0/80
17 Hibás válasz 257ms 113664 KiB
18 Elfogadva 256ms 113684 KiB
19 Hibás válasz 259ms 113640 KiB
20 Elfogadva 321ms 113864 KiB
21 Elfogadva 259ms 113852 KiB
22 Hibás válasz 263ms 113836 KiB
23 Elfogadva 261ms 113872 KiB
24 Elfogadva 259ms 113852 KiB
25 Hibás válasz 319ms 113772 KiB
26 Hibás válasz 316ms 114188 KiB
27 Elfogadva 286ms 114204 KiB
28 Elfogadva 314ms 114276 KiB
29 Hibás válasz 289ms 113796 KiB
30 Hibás válasz 321ms 114060 KiB
31 Elfogadva 323ms 114608 KiB
32 Elfogadva 289ms 117384 KiB
33 Elfogadva 333ms 120460 KiB
34 Elfogadva 333ms 129148 KiB
35 Hibás válasz 310ms 115604 KiB
36 Elfogadva 246ms 115448 KiB
37 Elfogadva 301ms 115144 KiB
38 Elfogadva 252ms 115020 KiB
39 Hibás válasz 298ms 114884 KiB
40 Hibás válasz 289ms 114008 KiB