Submission #879546

#TimeUsernameProblemLanguageResultExecution timeMemory
879546andrei_boacaHighway Tolls (IOI18_highway)C++17
Compilation error
0 ms0 KiB
#include "highway.h" #include <bits/stdc++.h> //#include "grader.cpp" using namespace std; typedef long long ll; typedef pair<int,int> pii; int n,m,niv[100005],par[100005],topar[100005],dp[21][100005],in[100005],out[100005],timp; ll dist; vector<pii> muchii[100005]; vector<pii> g; vector<int> w; bool isancestor(int a,int b) { return in[a]<=in[b]&&out[a]>=out[b]; } int LCA(int a,int b) { if(niv[a]>niv[b]) swap(a,b); if(isancestor(a,b)) return a; for(int i=20;i>=0;i--) if(dp[i][a]!=-1&&!isancestor(dp[i][a],b)) a=dp[i][a]; return par[a]; } void dfs(int nod) { timp++; in[nod]=timp; dp[0][nod]=par[nod]; for(int i=1;i<=20;i++) { if(dp[i-1][nod]==-1) { dp[i][nod]=-1; continue; } dp[i][nod]=dp[i-1][dp[i-1][nod]]; } for(auto i:muchii[nod]) if(i.first!=par[nod]) { par[i.first]=nod; niv[i.first]=niv[nod]+1; topar[i.first]=i.second; dfs(i.first); } out[nod]=timp; } void buildniv(int p) { for(int i=0;i<m;i++) { w[i]=1; if(min(niv[g[i].first],niv[g[i].second])<=p) w[i]=0; } } int getnode(vector<int> cand) { while(true) { if(cand.size()==1) return cand[0]; vector<int> x,y; int lg=cand.size(); for(int i=0;i<cand.size();i++) { if(i<lg/2) x.push_back(cand[i]); else y.push_back(cand[i]); } for(int i=0;i<m;i++) w[i]=1; for(int i:x) w[topar[i]]=0; ll val=ask(w); if(val<dist*B) cand=x; else cand=y; } return -1; } void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) { n=N; m=U.size(); for(int i=0;i<m;i++) { int a=U[i],b=V[i]; g.push_back({a,b}); muchii[a].push_back({b,i}); muchii[b].push_back({a,i}); } for(int i=0;i<n;i++) par[i]=-1; niv[0]=1; dfs(0); int nivmax=0; for(int i=0;i<n;i++) nivmax=max(nivmax,niv[i]); for(int i=0;i<m;i++) w.push_back(0); dist=ask(w)/A; int nivlca=nivmax; int st=1; int dr=nivmax-1; while(st<=dr) { int mij=(st+dr)/2; buildniv(mij); ll val=ask(w); if(val<dist*B) { nivlca=mij; dr=mij-1; } else st=mij+1; } int nivS=nivlca; int nivT=0; st=nivlca; dr=nivmax; while(st<=dr) { int mij=(st+dr)/2; buildniv(mij); ll nra=2*(mij-nivlca); if(nra<=dist) { ll val=ask(w); buildniv(mij-1); ll val2=ask(w); if(val2==val+2LL*(B-A)) { nivS=mij+1; st=mij+1; continue; } } dr=mij-1; } nivT=nivlca+(dist-(nivS-nivlca)); vector<int> c1,c2; if(nivS==nivT) { vector<int> cand; for(int i=0;i<n;i++) if(niv[i]==nivS) cand.push_back(i); while(true) { if(cand.size()==2) { c1.push_back(cand[0]); c2.push_back(cand[1]); break; } vector<int> x,y; int lg=cand.size(); for(int i=0;i<cand.size();i++) { if(i<lg/2) x.push_back(cand[i]); else y.push_back(cand[i]); } for(int i=0;i<m;i++) w[i]=1; for(int i:x) w[topar[i]]=0; ll val=ask(w); if(val==1LL*(dist-2)*B+2LL*A) { cand=x; continue; } if(val==dist*B) { cand=y; continue; } c1=x; c2=y; break; } } else { for(int i=0;i<n;i++) { if(niv[i]==nivS) c1.push_back(i); if(niv[i]==nivT) c2.push_back(i); } } int T=getnode(c2); c1.clear(); for(int i=0;i<n;i++) if(niv[i]==nivS&&niv[LCA(i,T)]==nivlca) c1.push_back(i); int S=getnode(c1); answer(S,T); }

Compilation message (stderr)

highway.cpp: In function 'int getnode(std::vector<int>)':
highway.cpp:68:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         for(int i=0;i<cand.size();i++)
      |                     ~^~~~~~~~~~~~
highway.cpp:80:21: error: 'B' was not declared in this scope
   80 |         if(val<dist*B)
      |                     ^
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:165:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  165 |             for(int i=0;i<cand.size();i++)
      |                         ~^~~~~~~~~~~~