Submission #415884

#	Time	Username	Problem	Language	Result	Execution time	Memory
415884		mosiashvililuka	Highway Tolls (IOI18_highway)	C++14	0 / 100	542 ms	19976 KiB

highway

#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;
}*/

Compilation message (stderr)

highway.cpp: In function 'int povna(int)':
highway.cpp:80:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |    for(jj=0; jj<dep[j].size(); jj++){
      |              ~~^~~~~~~~~~~~~~
highway.cpp:98:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |   for(jj=0; jj<dep[j].size(); jj++){
      |             ~~^~~~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:111:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |  for(i=0; i<UU.size(); i++){
      |           ~^~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 6
• Subtask 4: 0 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31