oj.uz

Submission #82447

# Submission time Handle Problem Language Result Execution time Memory
82447 2018-10-30T18:33:20 Z KLPP Highway Tolls (IOI18_highway) C++14
5 / 100
 320 ms 15400 KB 
#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);
}

Compilation message

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 324 KB Output is correct
2 Correct 2 ms 316 KB Output is correct
3 Correct 2 ms 320 KB Output is correct
4 Correct 2 ms 296 KB Output is correct
5 Correct 2 ms 316 KB Output is correct
6 Correct 2 ms 248 KB Output is correct
7 Correct 2 ms 312 KB Output is correct
8 Correct 2 ms 248 KB Output is correct
9 Correct 2 ms 404 KB Output is correct
10 Correct 2 ms 320 KB Output is correct
11 Correct 2 ms 320 KB Output is correct
12 Correct 2 ms 248 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 420 KB Output is correct
2 Correct 25 ms 1784 KB Output is correct
3 Correct 228 ms 13712 KB Output is correct
4 Correct 220 ms 13696 KB Output is correct
5 Correct 217 ms 13784 KB Output is correct
6 Correct 196 ms 13788 KB Output is correct
7 Correct 229 ms 13808 KB Output is correct
8 Correct 244 ms 13780 KB Output is correct
9 Correct 228 ms 13712 KB Output is correct
10 Correct 220 ms 13768 KB Output is correct
11 Correct 223 ms 13032 KB Output is correct
12 Correct 232 ms 13576 KB Output is correct
13 Correct 222 ms 13628 KB Output is correct
14 Incorrect 222 ms 13148 KB Output is incorrect: {s, t} is wrong.

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1704 KB Output is correct
2 Correct 41 ms 3044 KB Output is correct
3 Correct 57 ms 4400 KB Output is correct
4 Correct 152 ms 12332 KB Output is correct
5 Correct 164 ms 12344 KB Output is correct
6 Correct 181 ms 12476 KB Output is correct
7 Correct 177 ms 12916 KB Output is correct
8 Correct 167 ms 12448 KB Output is correct
9 Incorrect 177 ms 12812 KB Output is incorrect: {s, t} is wrong.

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 464 KB Output is correct
2 Correct 24 ms 1712 KB Output is correct
3 Correct 146 ms 10672 KB Output is correct
4 Correct 214 ms 13780 KB Output is correct
5 Correct 225 ms 13740 KB Output is correct
6 Correct 243 ms 13712 KB Output is correct
7 Correct 200 ms 13840 KB Output is correct
8 Correct 205 ms 13704 KB Output is correct
9 Correct 245 ms 13716 KB Output is correct
10 Correct 237 ms 13708 KB Output is correct
11 Incorrect 223 ms 13592 KB Output is incorrect: {s, t} is wrong.
12 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1848 KB Output is correct
2 Correct 25 ms 1936 KB Output is correct
3 Correct 232 ms 14388 KB Output is correct
4 Correct 265 ms 14960 KB Output is correct
5 Incorrect 320 ms 15400 KB Output is incorrect: {s, t} is wrong.
6 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1788 KB Output is correct
2 Correct 29 ms 1880 KB Output is correct
3 Correct 258 ms 13844 KB Output is correct
4 Correct 261 ms 14880 KB Output is correct
5 Incorrect 247 ms 14960 KB Output is incorrect: {s, t} is wrong.
6 Halted 0 ms 0 KB -