Submission #139076

#TimeUsernameProblemLanguageResultExecution timeMemory
139076ckodserHighway Tolls (IOI18_highway)C++14
12 / 100
534 ms17916 KiB
#include "highway.h" #include<bits/stdc++.h> #define ll long long #define pb push_back #define ld long double #define F first #define S second #define mp make_pair #define pii pair<ll,ll> using namespace :: std; const ll maxn=2e5+500; const ll inf=1e9+900; const ll mod=1e9+7; vector<ll> ger[maxn]; bool hazf[maxn]; ll s[maxn]; ll t[maxn]; ll sz[maxn]; ll st[maxn]; ll et[maxn]; ll tt=0; ll m,a,b,adi,n; vector<int> w; void dfsas(ll a,ll tim,ll p=-1){ for(auto e:ger[a]){ ll v=(s[e]^t[e]^a); if(v!=p && !hazf[v]){ if(et[v]<=tim){ w[e]=1; continue; } dfsas(v,tim,a); } } } ll as(vector<ll> vec,ll rot){ w.clear(); w.resize(m); fill(w.begin(),w.end(),0); dfsas(rot,et[vec.back()]); return ask(w); } ll finds(vector<ll> vec,ll rot){ if(vec.size()==1)return vec[0]; vector<ll> l,r; for(ll i=0;i<(ll)vec.size()/2;i++){ l.pb(vec[i]); } for(ll i=(ll)vec.size()/2;i<vec.size();i++){ r.pb(vec[i]); } if(as(l,rot)==adi+b-a){ return finds(l,rot); } return finds(r,rot); } pii findst(vector<ll> vec,ll rot){ if(vec.size()==2)return mp(vec[0],vec[1]); vector<ll> l,r; for(ll i=0;i<(ll)vec.size()/2;i++){ l.pb(vec[i]); } for(ll i=(ll)vec.size()/2;i<vec.size();i++){ r.pb(vec[i]); } ll p=as(l,rot); if(p==adi+b-a+b-a){ return findst(l,rot); } if(p==adi){ return findst(r,rot); } ll fa=finds(l,rot); adi+=b-a; ll fb=finds(r,rot); return mp(fa,fb); } vector<ll> topol; void dfsst(ll a,ll p=-1){ st[a]=tt; for(auto e:ger[a]){ ll v=(s[e]^t[e]^a); if(v!=p && !hazf[v]){ dfsst(v,a); } } topol.pb(a); et[a]=tt; tt++; } pii findAnsRot(ll rot){ tt=0; dfsst(rot); return findst(topol,rot); }/* void dfssz(ll a,ll p=-1){ sz[a]=1; for(auto e:ger[a]){ ll v=(s[e]^t[e]^a); if(v!=p && !hazf[v]){ dfssz(v,a); sz[a]+=sz[v]; } } } ll findCn(ll a,ll x,ll p=-1){ for(auto e:ger[a]){ ll v=(s[e]^t[e]^a); if(v!=p && !hazf[v] && sz[v]>x){ return findCn(v,x,a); } } return a; } void dfs(ll a){ dfssz(a); ll cn=findCn(a,sz[a]/2); dfssz(cn); vector<int> w(m); for(auto e:ger[cn]){ ll v=(s[e]^t[e]^cn); if(!hazf[v]){ w[e]=1; } } ll r=ask(w); if(r==adi){ }else{ } }*/ void find_pair(int N, vector<int> U, vector<int> V, int A, int B) { a=A; b=B; m=V.size(); n=N; if(m!=n-1){ exit(1); } for(ll i=0;i<m;i++){ s[i]=V[i]; t[i]=U[i]; } for(ll i=0;i<m;i++){ ger[s[i]].pb(i); ger[t[i]].pb(i); } vector<int> w(m); fill(w.begin(),w.end(),0); adi=ask(w); pii e=findAnsRot(0); answer(e.F,e.S); return ; // dfs(0); }

Compilation message (stderr)

highway.cpp: In function 'long long int finds(std::vector<long long int>, long long int)':
highway.cpp:56:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ll i=(ll)vec.size()/2;i<vec.size();i++){
                            ~^~~~~~~~~~~
highway.cpp: In function 'std::pair<long long int, long long int> findst(std::vector<long long int>, long long int)':
highway.cpp:70:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ll i=(ll)vec.size()/2;i<vec.size();i++){
                            ~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...