# | TimeUTC-0 | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1111945 | epicci23 | Highway Tolls (IOI18_highway) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "bits/stdc++.h"
#include "highway.h"
#define ll long long
#define all(v) v.begin() , v.end()
#define sz(a) (ll)a.size()
using namespace std;
const ll N = 2e5 + 5;
vector<ll> v[N],Xor,depth[N],Res;
ll n,m,A,B,Dist,vis[N],par[N],sub[N];
inline ll oth(ll c,ll u) {return Xor[c] ^ u;}
void upd(ll c,ll d){
sub[c]=1;
depth[d].push_back(c);
for(ll ind:v[c]){
ll x = oth(ind,c);
if(ind==par[c] || vis[x]) continue;
par[x]=ind;
upd(x,d+1);
sub[c]+=sub[x];
}
}
ll we_know_root(ll rt){
for(ll i=0;i<N;i++) depth[i].clear();
par[rt]=-1;
upd(rt,0);