1251 | 2022-03-28 22:34:48 | k_balint | Multiplikátoros telebabrátor | cpp14 | Elfogadva 100/100 | 421ms | 98588 KiB |
#include <bits/stdc++.h>
using namespace std;
const int c=1e5+5;
const int K=30;
struct edge{
int v,w;
edge(int vv, int ww){
v=vv; w=ww;
}
edge(){
v=w=0;
}
};
int trie[31*c][2];
int sz=1;
inline void add(int k){
int cur=0;
for(int i=K-1;i>=0;i--){
int j=(k>>i)&1;
if(!trie[cur][j]){
trie[cur][j]=sz++;
}
cur=trie[cur][j];
}
}
inline int maxi(int k){
int res=0; int cur=0;
for(int i=K-1;i>=0;i--){
int j=(k>>i)&1;
if(trie[cur][j^1]!=0){
res |= 1<<i;
cur=trie[cur][j^1];
}
else cur=trie[cur][j];
}
return res^k;
}
vector<edge> adj[c];
int d[c];
map<int,int> mp;
void dfs(int v, int p){
for(edge x:adj[v]){
if(x.v != p){
d[x.v]=d[v]^x.w;
dfs(x.v,v);
}
}
}
inline int read(){
int res=0; char ch=getchar();
while(!isdigit(ch)){
ch=getchar();
}
while(isdigit(ch)){
res=(res<<3)+(res<<1)+ch-'0';
ch=getchar();
}
return res;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n=read();
for(int i=1;i<n;i++){
int a,b,w; a=read(); b=read(); w=read();
adj[a].emplace_back(edge(b,w));
adj[b].emplace_back(edge(a,w));
}
dfs(1,0);
for(int i=1;i<=n;i++){
mp[d[i]]=i;
add(d[i]);
}
for(int i=1;i<=n;i++){
int cur=maxi(d[i]);
cout << mp[cur] << ' ';
}
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Elfogadva | 4ms | 6600 KiB | ||||
2 | Elfogadva | 6ms | 7660 KiB | ||||
subtask2 | 20/20 | ||||||
3 | Elfogadva | 6ms | 7636 KiB | ||||
4 | Elfogadva | 7ms | 7676 KiB | ||||
5 | Elfogadva | 6ms | 7724 KiB | ||||
6 | Elfogadva | 7ms | 7760 KiB | ||||
7 | Elfogadva | 8ms | 7800 KiB | ||||
8 | Elfogadva | 8ms | 7848 KiB | ||||
9 | Elfogadva | 6ms | 7880 KiB | ||||
10 | Elfogadva | 6ms | 7928 KiB | ||||
11 | Elfogadva | 6ms | 7972 KiB | ||||
12 | Elfogadva | 6ms | 8148 KiB | ||||
13 | Elfogadva | 6ms | 8236 KiB | ||||
14 | Elfogadva | 6ms | 8228 KiB | ||||
15 | Elfogadva | 6ms | 8136 KiB | ||||
16 | Elfogadva | 6ms | 8164 KiB | ||||
subtask3 | 80/80 | ||||||
17 | Elfogadva | 368ms | 49732 KiB | ||||
18 | Elfogadva | 275ms | 51836 KiB | ||||
19 | Elfogadva | 277ms | 53972 KiB | ||||
20 | Elfogadva | 298ms | 56108 KiB | ||||
21 | Elfogadva | 296ms | 58228 KiB | ||||
22 | Elfogadva | 291ms | 60352 KiB | ||||
23 | Elfogadva | 335ms | 62472 KiB | ||||
24 | Elfogadva | 286ms | 64584 KiB | ||||
25 | Elfogadva | 291ms | 66604 KiB | ||||
26 | Elfogadva | 286ms | 69036 KiB | ||||
27 | Elfogadva | 305ms | 71148 KiB | ||||
28 | Elfogadva | 282ms | 73268 KiB | ||||
29 | Elfogadva | 284ms | 75012 KiB | ||||
30 | Elfogadva | 421ms | 77140 KiB | ||||
31 | Elfogadva | 314ms | 79476 KiB | ||||
32 | Elfogadva | 300ms | 83464 KiB | ||||
33 | Elfogadva | 349ms | 87584 KiB | ||||
34 | Elfogadva | 331ms | 95100 KiB | ||||
35 | Elfogadva | 308ms | 88988 KiB | ||||
36 | Elfogadva | 287ms | 90944 KiB | ||||
37 | Elfogadva | 287ms | 92668 KiB | ||||
38 | Elfogadva | 275ms | 94836 KiB | ||||
39 | Elfogadva | 272ms | 96704 KiB | ||||
40 | Elfogadva | 310ms | 98588 KiB |