oj.uz

Submission #82462

# Submission time Handle Problem Language Result Execution time Memory
82462 2018-10-30T20:56:31 Z KLPP Highway Tolls (IOI18_highway) C++14
100 / 100
 547 ms 11516 KB 
#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

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

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 29 ms 1292 KB Output is correct
3 Correct 326 ms 9508 KB Output is correct
4 Correct 285 ms 9540 KB Output is correct
5 Correct 293 ms 9560 KB Output is correct
6 Correct 228 ms 9488 KB Output is correct
7 Correct 314 ms 9572 KB Output is correct
8 Correct 319 ms 9568 KB Output is correct
9 Correct 353 ms 9488 KB Output is correct
10 Correct 319 ms 9572 KB Output is correct
11 Correct 418 ms 8404 KB Output is correct
12 Correct 379 ms 8984 KB Output is correct
13 Correct 365 ms 9024 KB Output is correct
14 Correct 371 ms 8976 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 1192 KB Output is correct
2 Correct 55 ms 2180 KB Output is correct
3 Correct 64 ms 3068 KB Output is correct
4 Correct 184 ms 8428 KB Output is correct
5 Correct 201 ms 8432 KB Output is correct
6 Correct 205 ms 8592 KB Output is correct
7 Correct 222 ms 8956 KB Output is correct
8 Correct 178 ms 8528 KB Output is correct
9 Correct 186 ms 9008 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 25 ms 1152 KB Output is correct
3 Correct 255 ms 7380 KB Output is correct
4 Correct 387 ms 9548 KB Output is correct
5 Correct 321 ms 9472 KB Output is correct
6 Correct 356 ms 9488 KB Output is correct
7 Correct 326 ms 9480 KB Output is correct
8 Correct 312 ms 9488 KB Output is correct
9 Correct 323 ms 9484 KB Output is correct
10 Correct 357 ms 9480 KB Output is correct
11 Correct 350 ms 8976 KB Output is correct
12 Correct 253 ms 8604 KB Output is correct
13 Correct 384 ms 8980 KB Output is correct
14 Correct 416 ms 8452 KB Output is correct
15 Correct 317 ms 9480 KB Output is correct
16 Correct 362 ms 9628 KB Output is correct
17 Correct 353 ms 8968 KB Output is correct
18 Correct 389 ms 8976 KB Output is correct
19 Correct 389 ms 9496 KB Output is correct
20 Correct 387 ms 8996 KB Output is correct
21 Correct 230 ms 10036 KB Output is correct
22 Correct 250 ms 10028 KB Output is correct
23 Correct 283 ms 9208 KB Output is correct
24 Correct 204 ms 9032 KB Output is correct
25 Correct 230 ms 9000 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 1308 KB Output is correct
2 Correct 33 ms 1364 KB Output is correct
3 Correct 252 ms 9892 KB Output is correct
4 Correct 366 ms 10348 KB Output is correct
5 Correct 500 ms 11284 KB Output is correct
6 Correct 515 ms 11332 KB Output is correct
7 Correct 528 ms 10784 KB Output is correct
8 Correct 426 ms 10888 KB Output is correct
9 Correct 282 ms 7776 KB Output is correct
10 Correct 277 ms 8340 KB Output is correct
11 Correct 245 ms 8704 KB Output is correct
12 Correct 440 ms 9980 KB Output is correct
13 Correct 497 ms 10416 KB Output is correct
14 Correct 487 ms 10756 KB Output is correct
15 Correct 504 ms 11320 KB Output is correct
16 Correct 336 ms 8820 KB Output is correct
17 Correct 278 ms 9752 KB Output is correct
18 Correct 245 ms 10136 KB Output is correct
19 Correct 236 ms 10032 KB Output is correct
20 Correct 253 ms 10108 KB Output is correct
21 Correct 504 ms 11516 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 1340 KB Output is correct
2 Correct 23 ms 1496 KB Output is correct
3 Correct 476 ms 9432 KB Output is correct
4 Correct 477 ms 9548 KB Output is correct
5 Correct 463 ms 9840 KB Output is correct
6 Correct 463 ms 10860 KB Output is correct
7 Correct 401 ms 9848 KB Output is correct
8 Correct 402 ms 10240 KB Output is correct
9 Correct 515 ms 9896 KB Output is correct
10 Correct 547 ms 10744 KB Output is correct
11 Correct 494 ms 10828 KB Output is correct
12 Correct 506 ms 10924 KB Output is correct
13 Correct 296 ms 8720 KB Output is correct
14 Correct 304 ms 8140 KB Output is correct
15 Correct 274 ms 8816 KB Output is correct
16 Correct 244 ms 8248 KB Output is correct
17 Correct 247 ms 8740 KB Output is correct
18 Correct 296 ms 8172 KB Output is correct
19 Correct 470 ms 9996 KB Output is correct
20 Correct 508 ms 10944 KB Output is correct
21 Correct 544 ms 10828 KB Output is correct
22 Correct 517 ms 10800 KB Output is correct
23 Correct 530 ms 10836 KB Output is correct
24 Correct 451 ms 10868 KB Output is correct
25 Correct 506 ms 11328 KB Output is correct
26 Correct 491 ms 11320 KB Output is correct
27 Correct 214 ms 9900 KB Output is correct
28 Correct 271 ms 10016 KB Output is correct
29 Correct 263 ms 10068 KB Output is correct
30 Correct 266 ms 9944 KB Output is correct
31 Correct 294 ms 9896 KB Output is correct
32 Correct 230 ms 9776 KB Output is correct
33 Correct 286 ms 10240 KB Output is correct
34 Correct 242 ms 9916 KB Output is correct
35 Correct 304 ms 9904 KB Output is correct
36 Correct 254 ms 9876 KB Output is correct
37 Correct 257 ms 10068 KB Output is correct
38 Correct 227 ms 9996 KB Output is correct
39 Correct 520 ms 11316 KB Output is correct
40 Correct 501 ms 11324 KB Output is correct
41 Correct 331 ms 11344 KB Output is correct
42 Correct 506 ms 10788 KB Output is correct