제출 #1032846

#제출 시각아이디문제언어결과실행 시간메모리
1032846amirhoseinfar1385통행료 (IOI18_highway)C++17
0 / 100
7 ms5720 KiB
#include "highway.h" #include<bits/stdc++.h> using namespace std; const long long maxn=90000+10; long long n,a,b,aval,s,t; long long m,sz[maxn],vis[maxn]; vector<long long>adj[maxn]; struct yal{ long long u,v; long long getad(long long fu){ return (fu^v^u); } }alle[maxn]; long long pors(vector<long long>er){ vector<int>ret(m); for(auto x:er){ ret[x]=1; } return ask(ret); } void calsz(long long u,long long par=-1){ sz[u]=1; for(auto x:adj[u]){ long long v=alle[x].getad(u); if(vis[v]==0&&v!=par){ calsz(v,u); sz[u]+=sz[v]; } } } long long findcen(long long u,long long szz,long long par=-1){ for(auto x:adj[u]){ long long v=alle[x].getad(u); if(vis[v]==0&&sz[v]*2>szz&&v!=par){ return findcen(v,szz,u); } } return u; } long long finds(long long u=0){ // cout<<u<<endl; calsz(u); // cout<<u<<endl; long long v=findcen(u,sz[u]); // cout<<u<<endl; vector<long long>tof; for(auto x:adj[v]){ long long z=alle[x].getad(v); if(vis[z]==0){ tof.push_back(x); } } long long fake=pors(tof); if(fake==aval){ return v; } long long low=-1,high=(long long)tof.size(),mid; while(high-low>1){ mid=(high+low)>>1; vector<long long>ers; for(long long i=0;i<=mid;i++){ ers.push_back(tof[i]); } fake=pors(ers); if(fake==aval){ low=mid; }else{ high=mid; } } vis[v]=1; return finds(alle[tof[high]].getad(v)); } vector<long long>ham; long long bal[maxn]; void dfscal(long long u,long long len,long long par=-1,long long now=0){ if(now==len){ ham.push_back(u); return ; } for(auto x:adj[u]){ long long v=alle[x].getad(u); if(v==par){ continue; } bal[v]=x; dfscal(v,len,u,now+1); } } long long findt(){ dfscal(s,aval/a); long long low=-1,high=(long long)ham.size()-1,mid; while(high-low>1){ vector<long long>ers; mid=(high+low)>>1; for(long long i=0;i<=mid;i++){ ers.push_back(bal[ham[i]]); } long long fake=pors(ers); if(fake==aval){ low=mid; }else{ high=mid; } } return ham[high]; } void calc(){ // cout<<"av"<<endl; s=finds(); //s=0; // cout<<"dov"<<endl; t=findt(); } void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) { n=N; m = U.size(); a=A; b=B; for(long long i=0;i<m;i++){ alle[i].u=U[i]; alle[i].v=V[i]; adj[U[i]].push_back(i); adj[V[i]].push_back(i); } if(m!=n-1){ answer(0,1); return ; } aval=pors({}); calc(); //cout<<s<<" "<<t<<endl; answer(s,t); }
#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...