Submission #919090

#TimeUsernameProblemLanguageResultExecution timeMemory
919090velislavgarkovHighway Tolls (IOI18_highway)C++14
5 / 100
108 ms8816 KiB
#include "highway.h" #include <iostream> #include <vector> using namespace std; const int MAXN=1e5+10; vector <pair <int,int> > v[MAXN], dist; vector <int> w; int edge; long long a, b, path; int n; void find_tree(int x, int par) { for (auto i:v[x]) { if (i.second==edge) continue; if (i.first==par) continue; w[i.second]=1; find_tree(i.first,x); } } void dfs(int x, int par, int d) { for (auto i:v[x]) { if (i.second==edge) continue; if (i.first==par) continue; if (d==1) { dist.push_back(i); continue; } dfs(i.first,x,d-1); } } int find_one(int start) { for (int i=0;i<n-1;i++) w[i]=0; find_tree(start,start); long long d=(ask(w)-path)/(b-a); if (d==0) return start; if (!dist.empty()) dist.clear(); dfs(start,start,d); if (dist.empty()) return 1/0; int l, r, mid; l=0; r=dist.size()-1; while (l<r) { mid=(l+r)/2; for (int i=0;i<n-1;i++) w[i]=0; for (int i=l;i<=mid;i++) w[dist[i].second]=1; int cur=ask(w); if (cur==path) l=mid+1; else r=mid; } return dist[l].first; } void find_pair (int N, vector <int> U, vector <int> V, int A, int B) { n=N; a=A; b=B; w.resize(n-1); for (int i=0;i<n-1;i++) { v[U[i]].push_back({V[i],i}); v[V[i]].push_back({U[i],i}); } for (int i=0;i<n-1;i++) w[i]=0; path=ask(w); //cout << path << endl; edge=-1; int ans1, ans2; /* int l, r, mid; l=0; r=n-1; while (l<r) { mid=(l+r)/2; for (int i=0;i<n-1;i++) w[i]=0; for (int i=l;i<=mid;i++) w[i]=1; int cur=ask(w); if (cur==path) l=mid+1; else r=mid; } edge=l; //cout << U[edge] << ' ' << V[edge] << endl; ans1=find_one(U[edge]); ans2=find_one(V[edge]);*/ ans1=0; ans2=find_one(0); answer(ans1,ans2); }

Compilation message (stderr)

highway.cpp: In function 'int find_one(int)':
highway.cpp:37:31: warning: division by zero [-Wdiv-by-zero]
   37 |     if (dist.empty()) return 1/0;
      |                              ~^~
#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...