50902023-04-16 16:01:33szilMultiplikátoros telebabrátorcpp14Hibás válasz 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva4ms6672 KiB
2Elfogadva8ms9800 KiB
subtask20/20
3Hibás válasz8ms10012 KiB
4Elfogadva8ms10216 KiB
5Hibás válasz8ms10316 KiB
6Elfogadva8ms10364 KiB
7Hibás válasz8ms10612 KiB
8Hibás válasz8ms10488 KiB
9Elfogadva8ms10488 KiB
10Elfogadva8ms10484 KiB
11Elfogadva8ms10760 KiB
12Hibás válasz8ms11044 KiB
13Elfogadva8ms11216 KiB
14Hibás válasz8ms11252 KiB
15Hibás válasz8ms11140 KiB
16Hibás válasz8ms11124 KiB
subtask30/80
17Hibás válasz257ms113664 KiB
18Elfogadva256ms113684 KiB
19Hibás válasz259ms113640 KiB
20Elfogadva321ms113864 KiB
21Elfogadva259ms113852 KiB
22Hibás válasz263ms113836 KiB
23Elfogadva261ms113872 KiB
24Elfogadva259ms113852 KiB
25Hibás válasz319ms113772 KiB
26Hibás válasz316ms114188 KiB
27Elfogadva286ms114204 KiB
28Elfogadva314ms114276 KiB
29Hibás válasz289ms113796 KiB
30Hibás válasz321ms114060 KiB
31Elfogadva323ms114608 KiB
32Elfogadva289ms117384 KiB
33Elfogadva333ms120460 KiB
34Elfogadva333ms129148 KiB
35Hibás válasz310ms115604 KiB
36Elfogadva246ms115448 KiB
37Elfogadva301ms115144 KiB
38Elfogadva252ms115020 KiB
39Hibás válasz298ms114884 KiB
40Hibás válasz289ms114008 KiB