5089 | 2023-04-16 15:57:08 | szil | Multiplikátoros telebabrátor | cpp14 | Hibás válasz 0/100 | 321ms | 162144 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 | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Elfogadva | 4ms | 6672 KiB | ||||
2 | Elfogadva | 8ms | 9728 KiB | ||||
subtask2 | 0/20 | ||||||
3 | Hibás válasz | 8ms | 9984 KiB | ||||
4 | Elfogadva | 8ms | 10248 KiB | ||||
5 | Hibás válasz | 8ms | 10404 KiB | ||||
6 | Elfogadva | 8ms | 10644 KiB | ||||
7 | Hibás válasz | 8ms | 10812 KiB | ||||
8 | Hibás válasz | 8ms | 11084 KiB | ||||
9 | Elfogadva | 8ms | 11436 KiB | ||||
10 | Elfogadva | 8ms | 11444 KiB | ||||
11 | Elfogadva | 8ms | 11664 KiB | ||||
12 | Hibás válasz | 8ms | 11944 KiB | ||||
13 | Elfogadva | 8ms | 12420 KiB | ||||
14 | Hibás válasz | 8ms | 12132 KiB | ||||
15 | Hibás válasz | 8ms | 12168 KiB | ||||
16 | Hibás válasz | 8ms | 12340 KiB | ||||
subtask3 | 0/80 | ||||||
17 | Hibás válasz | 252ms | 110756 KiB | ||||
18 | Hibás válasz | 250ms | 112856 KiB | ||||
19 | Hibás válasz | 250ms | 115124 KiB | ||||
20 | Hibás válasz | 305ms | 117504 KiB | ||||
21 | Elfogadva | 256ms | 119660 KiB | ||||
22 | Hibás válasz | 307ms | 121720 KiB | ||||
23 | Hibás válasz | 305ms | 123868 KiB | ||||
24 | Elfogadva | 252ms | 126220 KiB | ||||
25 | Hibás válasz | 254ms | 128176 KiB | ||||
26 | Hibás válasz | 305ms | 130624 KiB | ||||
27 | Elfogadva | 308ms | 132972 KiB | ||||
28 | Hibás válasz | 252ms | 135160 KiB | ||||
29 | Hibás válasz | 316ms | 136680 KiB | ||||
30 | Hibás válasz | 312ms | 138836 KiB | ||||
31 | Hibás válasz | 314ms | 141348 KiB | ||||
32 | Elfogadva | 261ms | 146220 KiB | ||||
33 | Hibás válasz | 321ms | 151432 KiB | ||||
34 | Hibás válasz | 319ms | 162144 KiB | ||||
35 | Hibás válasz | 247ms | 150772 KiB | ||||
36 | Hibás válasz | 234ms | 152696 KiB | ||||
37 | Hibás válasz | 238ms | 154568 KiB | ||||
38 | Elfogadva | 236ms | 156640 KiB | ||||
39 | Hibás válasz | 232ms | 158508 KiB | ||||
40 | Hibás válasz | 248ms | 160016 KiB |