제출 #1197160

#제출 시각아이디문제언어결과실행 시간메모리
1197160simplemind_31Highway Tolls (IOI18_highway)C++20
18 / 100
278 ms327680 KiB
#include "highway.h" #include <bits/stdc++.h> #define ALL(x) x.begin(),x.end() using namespace std; typedef long long ll; vector<vector<pair<int,int>>> grafo; vector<int> dist; vector<pair<int,int>> padre; vector<int> vv,uu; int n,m,dist111,dist222; ll res,a,b; void dfs(int now,int ante){ for(auto u:grafo[now]){ if(u.first==ante){ continue; } padre[u.first].first=now; padre[u.first].second=u.second; dist[u.first]=dist[now]+1; dfs(u.first,now); } } int bs1(int xx,int ante){ dist.assign(n,-1); padre.assign(n,{-1,-1}); dist[xx]=0; padre[xx]={xx,-1}; dfs(xx,ante); vector<int> nuesort,cop; for(int i=0;i<n;i++){ if(dist[i]!=-1){ nuesort.push_back(dist[i]); } } sort(ALL(nuesort)); int nn=nuesort.size(); cop.push_back(nuesort[0]); for(int i=1;i<nn;i++){ if(cop.back()!=nuesort[i]){ cop.push_back(nuesort[i]); } } nuesort=cop; nn=nuesort.size(); int iz=0,de=nn-1,con=0,con1=0; while(iz<de){ vector<int> aske(m,0); int mid=(iz+de+1)>>1; for(int i=0;i<n;i++){ if(dist[i]==nuesort[mid]){ aske[padre[i].second]=1; } } if(res==ask(aske)){ de=mid-1; }else{ iz=mid; } } dist111=nuesort[iz]; if(nuesort[iz]==0){ return xx; } vector<int> aske(m,0),second; for(int i=0;i<n;i++){ if(dist[i]==nuesort[iz]){ aske[padre[i].second]=1; con++; } } ll resnow=res-a+b; while(con>1){ second=aske; con1=con; for(int i=0;i<m;i++){ if(second[i] && con1>(con/2)){ second[i]=0; con1--; } } if(ask(second)==resnow){ aske=second; con=con1; }else{ for(int i=0;i<m;i++){ if(second[i]>0){ aske[i]=0; } } con-=con1; } } for(int i=0;i<m;i++){ if(aske[i]){ if(padre[vv[i]].first==uu[i]){ return vv[i]; }else{ return uu[i]; } } } } int bs2(int xx,int ante){ dist.assign(n,-1); padre.assign(n,{-1,-1}); dist[xx]=0; padre[xx]={xx,-1}; dfs(xx,ante); int con=0,con1=0; dist222=res/a-dist111-1; if(dist222==0){ return xx; } vector<int> aske(m,0),second; for(int i=0;i<n;i++){ if(dist[i]==dist222){ aske[padre[i].second]=1; con++; } } ll resnow=res-a+b; while(con>1){ second=aske; con1=con; for(int i=0;i<m;i++){ if(second[i] && con1>(con/2)){ second[i]=0; con1--; } } if(ask(second)==resnow){ aske=second; con=con1; }else{ for(int i=0;i<m;i++){ if(second[i]>0){ aske[i]=0; } } con-=con1; } } for(int i=0;i<m;i++){ if(aske[i]){ if(padre[vv[i]].first==uu[i]){ return vv[i]; }else{ return uu[i]; } } } } void find_pair(int N,vector<int> U,vector<int> V, int A, int B){ a=A;b=B;n=N; m=U.size(); grafo.clear(); grafo.resize(n); vv=V; uu=U; for(int i=0;i<m;i++){ grafo[U[i]].push_back({V[i],i}); grafo[V[i]].push_back({U[i],i}); } vector<int> aske(m,0); res=ask(aske); int iz=0,de=m-1; while(iz<de){ aske.assign(m,0); int mid=(iz+de)>>1; for(int i=iz;i<=mid;i++){ aske[i]=1; } if(ask(aske)==res){ iz=mid+1; }else{ de=mid; } } int x=U[iz],y=V[iz]; int i=bs1(x,y),j=bs2(y,x); answer(i,j); }

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

highway.cpp: In function 'int bs1(int, int)':
highway.cpp:102:1: warning: control reaches end of non-void function [-Wreturn-type]
  102 | }
      | ^
highway.cpp: In function 'int bs2(int, int)':
highway.cpp:152:1: warning: control reaches end of non-void function [-Wreturn-type]
  152 | }
      | ^
#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...