50892023-04-16 15:57:08szilMultiplikátoros telebabrátorcpp14Hibás válasz 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva4ms6672 KiB
2Elfogadva8ms9728 KiB
subtask20/20
3Hibás válasz8ms9984 KiB
4Elfogadva8ms10248 KiB
5Hibás válasz8ms10404 KiB
6Elfogadva8ms10644 KiB
7Hibás válasz8ms10812 KiB
8Hibás válasz8ms11084 KiB
9Elfogadva8ms11436 KiB
10Elfogadva8ms11444 KiB
11Elfogadva8ms11664 KiB
12Hibás válasz8ms11944 KiB
13Elfogadva8ms12420 KiB
14Hibás válasz8ms12132 KiB
15Hibás válasz8ms12168 KiB
16Hibás válasz8ms12340 KiB
subtask30/80
17Hibás válasz252ms110756 KiB
18Hibás válasz250ms112856 KiB
19Hibás válasz250ms115124 KiB
20Hibás válasz305ms117504 KiB
21Elfogadva256ms119660 KiB
22Hibás válasz307ms121720 KiB
23Hibás válasz305ms123868 KiB
24Elfogadva252ms126220 KiB
25Hibás válasz254ms128176 KiB
26Hibás válasz305ms130624 KiB
27Elfogadva308ms132972 KiB
28Hibás válasz252ms135160 KiB
29Hibás válasz316ms136680 KiB
30Hibás válasz312ms138836 KiB
31Hibás válasz314ms141348 KiB
32Elfogadva261ms146220 KiB
33Hibás válasz321ms151432 KiB
34Hibás válasz319ms162144 KiB
35Hibás válasz247ms150772 KiB
36Hibás válasz234ms152696 KiB
37Hibás válasz238ms154568 KiB
38Elfogadva236ms156640 KiB
39Hibás válasz232ms158508 KiB
40Hibás válasz248ms160016 KiB