| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 415883 | mosiashvililuka | Highway Tolls (IOI18_highway) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,A,B,x,bo[200009],lef,rig,mid,dis[200009],fx[200009],C,D;
deque <int> de;
vector <int> dep[200009];
long long K,X;
vector <pair <int, int> > v[200009];
vector <int> U,V,vv;
/*int ask(vector <int> va){
int h=0,Ee;
for(h=0; h<va.size(); h++){
cout<<va[h]<<" ";
}
cout<<endl;
cin>>Ee;
return Ee;
}
void answer(int q, int w){
cout<<"! "<<q<<" "<<w;
exit(0);
}*/
void fun(){
int h=0;
for(h=0; h<b; h++) vv[h]=0;
for(h=1; h<=a; h++){
if(bo[h]==0) continue;
for(vector <pair <int, int> >::iterator it=v[h].begin(); it!=v[h].end(); it++){
vv[(*it).second]=1;
}
}
}
void rec(int q, int w){
int h=0;
if(q==w){
x=q;
return;
}
int mid=(q+w)/2;
for(h=q; h<=mid; h++){
bo[h]=1;
}
fun();
X=ask(vv);
if(K==X){
rec(mid+1,w);
}else{
for(h=q; h<=mid; h++){
bo[h]=0;
}
rec(q,mid);
}
}
int povna(int q){
x=q;
de.push_back(x);
for(i=1; i<=a; i++) fx[i]=0;
dis[x]=1;fx[x]=1;
while(de.size()){
c=de.front();
de.pop_front();
for(vector <pair <int, int> >::iterator it=v[c].begin(); it!=v[c].end(); it++){
if(fx[(*it).first]==1) continue;
dis[(*it).first]=dis[c]+1;
fx[(*it).first]=1;
de.push_back((*it).first);
}
}
for(i=1; i<=a; i++){
dep[dis[i]].push_back(i);
}
lef=1;rig=a+2;
while(1){
if(lef+1>=rig) break;
mid=(lef+rig)/2;
for(i=1; i<=a; i++) bo[i]=0;
zx=a+1-mid;
// cout<<"mid "<<mid<<" "<<zx<<endl;
for(j=a; j>=1; j--){
for(jj=0; jj<dep[j].size(); jj++){
if(zx==0) break;
zx--;
bo[dep[j][jj]]=1;
}
if(zx==0) break;
}
fun();
X=ask(vv);
if(K==X){
rig=mid;
}else{
lef=mid;
}
}
mid=lef;
zx=a+1-mid;xc=0;
for(j=a; j>=1; j--){
for(jj=0; jj<dep[j].size(); jj++){
if(zx==0) break;
zx--;
xc=dep[j][jj];
}
if(zx==0) break;
}
return xc;
}
void find_pair(int N, vector<int> UU, vector<int> VV, int AA, int BB) {
a=N;b=UU.size();
A=AA;B=BB;
vv.resize(b);
for(i=0; i<UU.size(); i++){
U.push_back(UU[i]);V.push_back(VV[i]);
U[i]++;V[i]++;
v[U[i]].push_back(make_pair(V[i],i));
v[V[i]].push_back(make_pair(U[i],i));
}
for(i=0; i<b; i++) vv[i]=0;
K=ask(vv);
rec(1,a);
// cout<<"X "<<x<<endl;
C=povna(x);
D=povna(C);
answer(C-1,D-1);
}
/*int main(){
ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int N,M,S,T;
cin>>N>>M>>A>>B>>S>>T;
vector <int> UU,VV;
for(i=1; i<=M; i++){
cin>>c>>d;
UU.push_back(c);VV.push_back(d);
}
find_pair(N,UU,VV,A,B);
return 0;
}*/