Submission #82462

#	Time	Username	Problem	Language	Result	Execution time	Memory
82462		KLPP	Highway Tolls (IOI18_highway)	C++14	100 / 100	547 ms	11516 KiB

highway

#include "highway.h"
#include<vector>
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
typedef pair<int,int> pii;
typedef long long int lld;

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	int m=U.size();
	int lo=0;
	int hi=m-1;
	vector<int> NN(m);
	lld u=ask(NN);
	//cout<<u<<endl;
	while(hi>lo){//cout<<lo<<" "<<hi<<endl;
		int mid=(hi+lo)/2;
		vector<int> v(m);
		for(int i=0;i<=mid;i++)v[i]=1;
		lld h=ask(v);
		if(h>u){
			hi=mid;
		}else lo=mid+1;
	}//cout<<hi<<endl;
	//cout<<hi<<endl;
	vector<pair<int,int> > nei[N];
	for(int i=0;i<m;i++){
		nei[U[i]].push_back(pair<int,int>(V[i],i));
		nei[V[i]].push_back(pair<int,int>(U[i],i));
	}
	queue<int> q;
	int dist[N];
	bool CC[N];
	for(int i=0;i<N;i++){
		dist[i]=-1;
		CC[i]=false;
	}
	CC[V[hi]]=true;
	dist[U[hi]]=0;
	dist[V[hi]]=0;
	q.push(U[hi]);
	q.push(V[hi]);
	//tree.push_back(hi);
	
	while(!q.empty()){
		int U=q.front();q.pop();
		for(int i=0;i<nei[U].size();i++){
			int V=nei[U][i].first;
			if(dist[V]==-1){
				dist[V]=dist[U]+1;
				q.push(V);
				//nei[U].push_back(pii(V,nei[U][i].second));
				//nei[V].push_back(pii(U,nei[U][i].second));
				//cout<<nei[U][i].second<<endl;
				CC[V]=CC[U];
				//parent[V]=nei[U][i].second;
			}
		}
	}
	/*for(int i=0;i<N;i++){
		cout<<CC[i]<<" "<<dist[i]<<endl;
	}*/
	//OK
	vector<pii> VV;
	for(int i=0;i<N;i++){
		if(!CC[i] && dist[i]>0){
			VV.push_back(pii(dist[i],i));
			//cout<<dist[i]<<" "<<parent[i]<<endl;
		}
	}sort(VV.begin(),VV.end());
	int XX=U[hi];
	int YY=V[hi];
	//cout<<XX<<" "<<YY<<endl;
	lo=-1;
	hi=VV.size();
	while(hi-lo>1){
		int mid=(hi+lo)/2;
		vector<int> asking(m);
		for(int i=mid;i<VV.size();i++){
			int vertex=VV[i].second;
			for(int i=0;i<nei[vertex].size();i++)asking[nei[vertex][i].second]=1;
		}
		//for(int i=0;i<N;i++)cout<<asking[i];
		//cout<<endl;
		lld R=ask(asking);
		//cout<<R<<" "<<u<<endl;
		if(R>u)lo=mid;
		else hi=mid;
	}
	//cout<<lo<<" "<<hi<<endl;
	//cout<<VV[lo].second<<endl;
	int S=-1;
	//cout<<lo<<endl;
	if(lo==-1)S=XX;
	else{
		S=VV[lo].second;
	}
	//cout<<S<<endl;
	VV.clear();
	for(int i=0;i<N;i++){
		if(CC[i] && dist[i]>0){//cout<<i<<endl;
			VV.push_back(pii(dist[i],i));
			//cout<<dist[i]<<" "<<parent[i]<<endl;
		}
	}sort(VV.begin(),VV.end());
	//for(int i=0;i<VV.size();i++)cout<<VV[i].first.first<<" "<<VV[i].first.second<<" "<<VV[i].second<<endl;
	lo=-1;
	hi=VV.size();
	//cout<<lo<<" "<<hi<<endl;
	while(hi-lo>1){//cout<<lo<<" "<<hi<<endl;
		int mid=(hi+lo)/2;
		vector<int> asking(m);
		for(int i=mid;i<VV.size();i++){
			int vertex=VV[i].second;
			for(int i=0;i<nei[vertex].size();i++){
				asking[nei[vertex][i].second]=1;
			}
		}
		lld R=ask(asking);
		//cout<<R<<" "<<u<<" "<<mid<<endl;
		if(R>u)lo=mid;
		else hi=mid;
	}
	//cout<<lo<<" "<<hi<<endl;
	//cout<<VV[lo].second<<endl;
	int T=-1;
	if(lo==-1)T=YY;
	else{
		T=VV[lo].second;
	}
	/*cout<<XX<<" "<<YY<<endl;
	//cout<<nei[XX].size()<<" "<<nei[YY].size()<<endl;
	for(int i=0;i<nei[XX].size();i++){
		cout<<nei[XX][i].first<<endl;
	}
	for(int i=0;i<nei[YY].size();i++){
		cout<<nei[YY][i].first<<endl;
	}
	cout<<S<<" "<<T<<endl;*/
	answer(S,T);
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:48:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<nei[U].size();i++){
               ~^~~~~~~~~~~~~~
highway.cpp:80:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=mid;i<VV.size();i++){
                 ~^~~~~~~~~~
highway.cpp:82:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i<nei[vertex].size();i++)asking[nei[vertex][i].second]=1;
                ~^~~~~~~~~~~~~~~~~~~
highway.cpp:114:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=mid;i<VV.size();i++){
                 ~^~~~~~~~~~
highway.cpp:116:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i<nei[vertex].size();i++){
                ~^~~~~~~~~~~~~~~~~~~

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