제출 #382279

#제출 시각아이디문제언어결과실행 시간메모리
382279sad통행료 (IOI18_highway)C++14
6 / 100
135 ms11676 KiB
#include<bits/stdc++.h> #include "highway.h" #define pb push_back #define fi first #define se second using namespace std; long long a,b,n;const int N=90090; int pa[N],what[N],in[N];long long l;vector<int>vv;vector<pair<int,int>>v[N]; vector<int>w; void dfs(int x,int p,long long le) { pa[x]=p; if(le==0){ vv.pb(x);return; } for(auto it:v[x]) { if(it.se==p)continue; dfs(it.fi,it.se,le-1); } } int ch(int ll,int r) { w.clear(); for(int i=0;i<n-1;i++)w.pb(0); for(int i=ll;i<=r;i++) { w[pa[vv[i]]]=1; } long long x=ask(w); w.clear(); long long y=a*l; if(x>y)return 1; return 0; } int chee(int ll,int r) { w.clear(); for(int i=0;i<n-1;i++)w.pb(0); for(int i=ll;i<=r;i++) { w[pa[what[i]]]=1; } long long x=ask(w); w.clear(); long long y=a*l; if(x>y)return 1; return 0; } int timer=-1; void go (int x,int p) { pa[x]=p; in[x]=++timer; what[timer]=x; for(auto it:v[x]) { if(it.se==p)continue; go(it.fi,it.se); } } void find_pair(int N, vector<int> U, vector<int> V, int A, int B) { a=A;b=B; w.clear(); n=N; for(int i=0;i<n-1;i++)w.pb(0); l=ask(w)/a; for(int i=0;i<n-1;i++) { v[V[i]].pb({U[i],i}); v[U[i]].pb({V[i],i}); } go(0,-1); int st=0,end=timer; while(st<end) { int mid=(st+end)/2; if(chee(mid+1,end)) { st=mid+1; } else end=mid; } int point=st; dfs(point,-1,l); int m=vv.size(); st=0,end=m-1; while(st<end) { int mid=st+end;mid/=2; if(ch(st,mid)) end=mid; else st=mid+1; } answer(point,vv[st]); } /* 4 3 1 2 1 2 1 2 1 0 1 3 */
#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...