12512022-03-28 22:34:48k_balintMultiplikátoros telebabrátorcpp14Elfogadva 100/100421ms98588 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ÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva4ms6600 KiB
2Elfogadva6ms7660 KiB
subtask220/20
3Elfogadva6ms7636 KiB
4Elfogadva7ms7676 KiB
5Elfogadva6ms7724 KiB
6Elfogadva7ms7760 KiB
7Elfogadva8ms7800 KiB
8Elfogadva8ms7848 KiB
9Elfogadva6ms7880 KiB
10Elfogadva6ms7928 KiB
11Elfogadva6ms7972 KiB
12Elfogadva6ms8148 KiB
13Elfogadva6ms8236 KiB
14Elfogadva6ms8228 KiB
15Elfogadva6ms8136 KiB
16Elfogadva6ms8164 KiB
subtask380/80
17Elfogadva368ms49732 KiB
18Elfogadva275ms51836 KiB
19Elfogadva277ms53972 KiB
20Elfogadva298ms56108 KiB
21Elfogadva296ms58228 KiB
22Elfogadva291ms60352 KiB
23Elfogadva335ms62472 KiB
24Elfogadva286ms64584 KiB
25Elfogadva291ms66604 KiB
26Elfogadva286ms69036 KiB
27Elfogadva305ms71148 KiB
28Elfogadva282ms73268 KiB
29Elfogadva284ms75012 KiB
30Elfogadva421ms77140 KiB
31Elfogadva314ms79476 KiB
32Elfogadva300ms83464 KiB
33Elfogadva349ms87584 KiB
34Elfogadva331ms95100 KiB
35Elfogadva308ms88988 KiB
36Elfogadva287ms90944 KiB
37Elfogadva287ms92668 KiB
38Elfogadva275ms94836 KiB
39Elfogadva272ms96704 KiB
40Elfogadva310ms98588 KiB