제출 #114278

#제출 시각아이디문제언어결과실행 시간메모리
114278faustaadp통행료 (IOI18_highway)C++17
51 / 100
318 ms44708 KiB
#include "highway.h" #include<bits/stdc++.h> typedef long long ll; #define pb push_back #define mp make_pair #define fi first #define se second using namespace std; ll m,i,x[202020],y[202020],jarak,p[202020],te,o[202020]; vector<ll> v[202020],w[202020]; vector<int> z,q1,q2; void dfs(ll aa,ll bb,ll cc) { p[aa]=bb; //dep[aa]=cc; ll ii; for(ii=0;ii<v[aa].size();ii++) if(v[aa][ii]!=bb) { x[++te]=w[aa][ii]; y[te]=v[aa][ii]; o[w[aa][ii]]=v[aa][ii]; dfs(v[aa][ii],aa,cc+1); } } void dfs1(ll aa) { ll ii; for(ii=0;ii<v[aa].size();ii++) if(v[aa][ii]!=p[aa]) { // cout<<w[aa][ii]<<"_\n"; z[w[aa][ii]]=0; dfs1(v[aa][ii]); } } void dfs2(ll aa,ll bb) { ll ii; for(ii=0;ii<v[aa].size();ii++) if(v[aa][ii]!=p[aa]) { if(bb==1) { q1.pb(w[aa][ii]); } dfs2(v[aa][ii],bb-1); } } void dfs3(ll aa,ll bb,ll cc) { ll ii; for(ii=0;ii<v[aa].size();ii++) if(v[aa][ii]!=p[aa]&&v[aa][ii]!=cc) { if(bb==1) q2.pb(w[aa][ii]); dfs3(v[aa][ii],bb-1,cc); } } void ubah(ll aa,ll bb,ll cc) { ll ii; for(ii=aa;ii<=bb;ii++) z[x[ii]]=cc; } void ubah1(ll aa,ll bb,ll cc) { ll ii; for(ii=aa;ii<=bb;ii++) z[q1[ii]]=cc; } void ubah2(ll aa,ll bb,ll cc) { ll ii; for(ii=aa;ii<=bb;ii++) z[q2[ii]]=cc; } void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) { m = U.size(); for(i=0;i<m;i++) { v[U[i]].pb(V[i]); w[U[i]].pb(i); v[V[i]].pb(U[i]); w[V[i]].pb(i); } dfs(0,0,0); ll L=0,R=m-1,C,H; for(i=0;i<m;i++) z.pb(0); ll tem=ask(z); jarak=tem/A; ask(z); while(L<=R) { C=(L+R)/2; ubah(1,C,1); ubah(C+1,m,0); if(ask(z)==tem) { H=C+1; L=C+1; } else R=C-1; } ubah(1,m,1); z[x[H]]=0; dfs1(y[H]); ll tom=ask(z); //for(i=0;i<m;i++) // cout<<i<<" "<<z[i]<<"\n"; //cout<<y [H]<<" "<<H<<" "<<tom<<" "<<tem<<"\n"; if(tom==tem) { if(jarak==1) { answer(y[H],p[y[H]]); } else { dfs2(y[H],jarak-1); L=0; R=q1.size()-1; ll H1; while(L<=R) { C=(L+R)/2; ubah1(0,C,0); ubah1(C+1,q1.size()-1,1); if(ask(z)==tem) { H1=C; R=C-1; } else L=C+1; } answer(o[q1[H1]],p[y[H]]); } //cout<<"A"; } else { ll jer=jarak-((tom-tem)/(B-A)),H1,H2; if(jer==1) H1=y[H]; else { dfs2(y[H],jer-1); //cout<<jer<<"\n"; L=0; R=q1.size()-1; ubah(1,m,0); //for(i=0;i<q1.size();i++) // cout<<q1[i]<<"*\n"; while(L<=R) { C=(L+R)/2; ubah1(0,C,0); ubah1(C+1,q1.size()-1,1); if(ask(z)==tem) { // cout<<C<<"_()\n"; H1=o[q1[C]]; R=C-1; } else L=C+1; } // cout<<H1<<"\n"; } ubah(1,m,0); dfs3(p[y[H]],jarak-jer,y[H]); L=0; R=q2.size()-1; //for(i=0;i<q2.size();i++) // cout<<q2[i]<<"_\n"; while(L<=R) { C=(L+R)/2; ubah2(0,C,0); ubah2(C+1,q2.size()-1,1); if(ask(z)==tem) { H2=o[q2[C]]; R=C-1; } else L=C+1; } //cout<<H1<<" "<<H2<<"\n"; answer(H1, H2); } }

컴파일 시 표준 에러 (stderr) 메시지

highway.cpp: In function 'void dfs(ll, ll, ll)':
highway.cpp:17:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ii=0;ii<v[aa].size();ii++)
           ~~^~~~~~~~~~~~~
highway.cpp: In function 'void dfs1(ll)':
highway.cpp:29:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ii=0;ii<v[aa].size();ii++)
           ~~^~~~~~~~~~~~~
highway.cpp: In function 'void dfs2(ll, ll)':
highway.cpp:40:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ii=0;ii<v[aa].size();ii++)
           ~~^~~~~~~~~~~~~
highway.cpp: In function 'void dfs3(ll, ll, ll)':
highway.cpp:53:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ii=0;ii<v[aa].size();ii++)
           ~~^~~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:195:9: warning: 'H2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   answer(H1, H2);
   ~~~~~~^~~~~~~~
highway.cpp:195:9: warning: 'H1' may be used uninitialized in this function [-Wmaybe-uninitialized]
highway.cpp:141:18: warning: 'H1' may be used uninitialized in this function [-Wmaybe-uninitialized]
    answer(o[q1[H1]],p[y[H]]);
                  ^
highway.cpp:111:6: warning: 'H' may be used uninitialized in this function [-Wmaybe-uninitialized]
  dfs1(y[H]); 
  ~~~~^~~~~~
#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...