Submission #117002

#TimeUsernameProblemLanguageResultExecution timeMemory
117002dsjongHighway Tolls (IOI18_highway)C++14
12 / 100
423 ms262148 KiB
#include "highway.h" #include <bits/stdc++.h> using namespace std; int NN; long long AA,BB,CNT; vector<int>adj[100005]; int dep[100005],par[100005]; int mp[100005]; vector<int>leaves; void dfs(int i,int p){ par[i]=p; for(int j:adj[i]){ if(j==p) continue; dep[j]=dep[i]+1; dfs(j,i); } } bool pick[100005]; bool vis[100005]; vector<int>query; bool check(int L,int R){ query.clear(); memset(pick,0,sizeof pick); memset(vis,0,sizeof vis); for(int i=L;i<=R;i++){ int cur=leaves[i]; while(!vis[cur]&&cur!=0){ pick[mp[cur]]=true; vis[cur]=true; cur=par[cur]; } } int cnt=0; for(int i=0;i<NN-1;i++){ if(pick[i]){ query.push_back(1); cnt++; } else query.push_back(0); } long long x=ask(query); if(x/BB>=CNT) return true; return false; } void find_pair(int n, std::vector<int> U, std::vector<int> V, int a, int b) { NN=n,AA=a,BB=b; for(int i=0;i<U.size();i++){ adj[U[i]].push_back(V[i]); adj[V[i]].push_back(U[i]); } dep[0]=0; dfs(0,-1); for(int i=0;i<U.size();i++){ if(par[U[i]]==V[i]) mp[U[i]]=i; else mp[V[i]]=i; } query.clear(); for(int i=0;i<NN-1;i++){ query.push_back(0); } CNT=ask(query)/AA; //cout<<CNT<<endl; for(int i=1;i<NN;i++){ if(adj[i].size()==1) leaves.push_back(i); } /*for(int i:leaves) cout<<i<<" "; cout<<endl;*/ int L=0,R=leaves.size()-1; while(L<R){ //cout<<L<<" "<<R<<" "; if(R==L+1){ if(check(L,L)) R=L; else L=R; break; } int M=(L+R)/2; if(check(L,M)) R=M; else L=M+1; } int ans=leaves[L]; for(int i=0;i<dep[leaves[L]]-CNT;i++){ ans=par[ans]; //cout<<ans<<endl; } answer(ans,0); }

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:47:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<U.size();i++){
              ~^~~~~~~~~
highway.cpp:53:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<U.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...