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