제출 #82447

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
82447		KLPP	통행료 (IOI18_highway)	C++14	5 / 100	320 ms	15400 KiB

highway

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

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);
	int u=ask(NN);
	while(hi>lo){//cout<<lo<<" "<<hi<<endl;
		int mid=(hi+lo)/2;
		vector<int> v(m);
		for(int i=lo;i<=mid;i++)v[i]=1;
		int 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]);
	vector<int> tree[N];
	//tree.push_back(hi);
	int parent[N];
	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;
	}*/
	vector<pii> VV;
	for(int i=0;i<N;i++){
		if(!CC[i] && dist[i]>0){
			VV.push_back(pii(dist[i],parent[i]));
			//cout<<dist[i]<<" "<<parent[i]<<endl;
		}
	}sort(VV.begin(),VV.end());
	int XX=U[hi];
	int YY=V[hi];
	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++)asking[VV[i].second]=1;
		//for(int i=0;i<N;i++)cout<<asking[i];
		//cout<<endl;
		int 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;
	if(lo==-1)S=XX;
	else{
		if(dist[U[VV[lo].second]]<dist[V[VV[lo].second]])S=V[VV[lo].second];
		else S=U[VV[lo].second];
	}
	//cout<<S<<endl;
	VV.clear();
	for(int i=0;i<N;i++){
		if(CC[i] && dist[i]>0){
			VV.push_back(pii(dist[i],parent[i]));
			//cout<<dist[i]<<" "<<parent[i]<<endl;
		}
	}sort(VV.begin(),VV.end());
	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++)asking[VV[i].second]=1;
		//for(int i=0;i<N;i++)cout<<asking[i];
		//cout<<endl;
		int 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 T=-1;
	if(lo==-1)T=YY;
	else{
		if(dist[U[VV[lo].second]]<dist[V[VV[lo].second]])T=V[VV[lo].second];
		else T=U[VV[lo].second];
	}
	//cout<<S<<" "<<T<<endl;
	answer(S,T);
}

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

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

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