oj.uz

Submission #82460

# Submission time Handle Problem Language Result Execution time Memory
82460 2018-10-30T19:38:53 Z KLPP Highway Tolls (IOI18_highway) C++14
51 / 100
 512 ms 13496 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=lo;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){
			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();
	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<<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:113:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=mid;i<VV.size();i++){
                 ~^~~~~~~~~~
highway.cpp:115: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;
                ~^~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 31 ms 1580 KB Output is correct
3 Correct 365 ms 11236 KB Output is correct
4 Correct 313 ms 11344 KB Output is correct
5 Correct 305 ms 11308 KB Output is correct
6 Correct 228 ms 11280 KB Output is correct
7 Correct 347 ms 11336 KB Output is correct
8 Correct 427 ms 11324 KB Output is correct
9 Correct 444 ms 11280 KB Output is correct
10 Correct 316 ms 11276 KB Output is correct
11 Correct 422 ms 10668 KB Output is correct
12 Correct 360 ms 11148 KB Output is correct
13 Correct 385 ms 11064 KB Output is correct
14 Correct 354 ms 11156 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1576 KB Output is correct
2 Correct 47 ms 2552 KB Output is correct
3 Correct 68 ms 3540 KB Output is correct
4 Correct 171 ms 9940 KB Output is correct
5 Correct 195 ms 9868 KB Output is correct
6 Correct 168 ms 10124 KB Output is correct
7 Correct 208 ms 10392 KB Output is correct
8 Correct 184 ms 9980 KB Output is correct
9 Correct 190 ms 10400 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 32 ms 1448 KB Output is correct
3 Correct 278 ms 8768 KB Output is correct
4 Correct 407 ms 11424 KB Output is correct
5 Correct 454 ms 11276 KB Output is correct
6 Correct 394 ms 11284 KB Output is correct
7 Correct 405 ms 11248 KB Output is correct
8 Correct 341 ms 11280 KB Output is correct
9 Correct 353 ms 11284 KB Output is correct
10 Correct 362 ms 11280 KB Output is correct
11 Correct 313 ms 11108 KB Output is correct
12 Correct 272 ms 10772 KB Output is correct
13 Correct 362 ms 11172 KB Output is correct
14 Correct 424 ms 10612 KB Output is correct
15 Correct 444 ms 11288 KB Output is correct
16 Correct 461 ms 11408 KB Output is correct
17 Correct 340 ms 11148 KB Output is correct
18 Correct 353 ms 11156 KB Output is correct
19 Correct 429 ms 11292 KB Output is correct
20 Correct 410 ms 11136 KB Output is correct
21 Correct 270 ms 10728 KB Output is correct
22 Correct 259 ms 10740 KB Output is correct
23 Correct 279 ms 9856 KB Output is correct
24 Correct 231 ms 10132 KB Output is correct
25 Correct 283 ms 11152 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 1552 KB Output is correct
2 Correct 33 ms 1616 KB Output is correct
3 Correct 307 ms 11868 KB Output is correct
4 Correct 395 ms 12524 KB Output is correct
5 Correct 512 ms 12868 KB Output is correct
6 Incorrect 339 ms 13496 KB Output is incorrect: {s, t} is wrong.
7 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 1448 KB Output is correct
2 Correct 29 ms 1612 KB Output is correct
3 Correct 471 ms 11428 KB Output is correct
4 Incorrect 402 ms 12396 KB Output is incorrect: {s, t} is wrong.
5 Halted 0 ms 0 KB -