oj.uz

Submission #82458

# Submission time Handle Problem Language Result Execution time Memory
82458 2018-10-30T19:30:12 Z KLPP Highway Tolls (IOI18_highway) C++14
51 / 100
 314 ms 15876 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]);
	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;
	}*/
	//OK
	vector<pair<pii,int> > VV;
	for(int i=0;i<N;i++){
		if(!CC[i] && dist[i]>0){
			VV.push_back(pair<pii,int>(pii(dist[i],i),parent[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++)asking[VV[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].first.second;
	}
	//cout<<S<<endl;
	VV.clear();
	for(int i=0;i<N;i++){
		if(CC[i] && dist[i]>0){
			VV.push_back(pair<pii,int>(pii(dist[i],i),parent[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++)asking[VV[i].second]=1;
		/*for(int i=0;i<m;i++)cout<<asking[i];
		cout<<endl;*/
		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].first.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:49:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<nei[U].size();i++){
               ~^~~~~~~~~~~~~~
highway.cpp:81: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:111: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 376 KB Output is correct
2 Correct 2 ms 252 KB Output is correct
3 Correct 2 ms 328 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 2 ms 400 KB Output is correct
6 Correct 2 ms 248 KB Output is correct
7 Correct 2 ms 268 KB Output is correct
8 Correct 2 ms 320 KB Output is correct
9 Correct 2 ms 408 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 324 KB Output is correct
12 Correct 2 ms 408 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 16 ms 1932 KB Output is correct
3 Correct 236 ms 14092 KB Output is correct
4 Correct 249 ms 14208 KB Output is correct
5 Correct 212 ms 14092 KB Output is correct
6 Correct 223 ms 14100 KB Output is correct
7 Correct 242 ms 14200 KB Output is correct
8 Correct 244 ms 14172 KB Output is correct
9 Correct 229 ms 14100 KB Output is correct
10 Correct 249 ms 14092 KB Output is correct
11 Correct 233 ms 13204 KB Output is correct
12 Correct 235 ms 13968 KB Output is correct
13 Correct 232 ms 14072 KB Output is correct
14 Correct 215 ms 13964 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1832 KB Output is correct
2 Correct 43 ms 3132 KB Output is correct
3 Correct 94 ms 4480 KB Output is correct
4 Correct 178 ms 12448 KB Output is correct
5 Correct 178 ms 12452 KB Output is correct
6 Correct 174 ms 13284 KB Output is correct
7 Correct 184 ms 13312 KB Output is correct
8 Correct 179 ms 12532 KB Output is correct
9 Correct 179 ms 13192 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 552 KB Output is correct
2 Correct 26 ms 1792 KB Output is correct
3 Correct 172 ms 11564 KB Output is correct
4 Correct 229 ms 14104 KB Output is correct
5 Correct 243 ms 14104 KB Output is correct
6 Correct 213 ms 14104 KB Output is correct
7 Correct 215 ms 14100 KB Output is correct
8 Correct 222 ms 14096 KB Output is correct
9 Correct 248 ms 14100 KB Output is correct
10 Correct 244 ms 14104 KB Output is correct
11 Correct 239 ms 14060 KB Output is correct
12 Correct 201 ms 13704 KB Output is correct
13 Correct 244 ms 13968 KB Output is correct
14 Correct 224 ms 13208 KB Output is correct
15 Correct 219 ms 14080 KB Output is correct
16 Correct 233 ms 14088 KB Output is correct
17 Correct 234 ms 14020 KB Output is correct
18 Correct 236 ms 14024 KB Output is correct
19 Correct 235 ms 14096 KB Output is correct
20 Correct 229 ms 14100 KB Output is correct
21 Correct 207 ms 14192 KB Output is correct
22 Correct 200 ms 14208 KB Output is correct
23 Correct 205 ms 12772 KB Output is correct
24 Correct 196 ms 13052 KB Output is correct
25 Correct 222 ms 13972 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 1848 KB Output is correct
2 Correct 31 ms 2044 KB Output is correct
3 Correct 246 ms 14436 KB Output is correct
4 Correct 279 ms 15084 KB Output is correct
5 Incorrect 314 ms 15876 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 29 ms 1852 KB Output is correct
2 Correct 34 ms 2004 KB Output is correct
3 Correct 241 ms 14108 KB Output is correct
4 Correct 277 ms 14812 KB Output is correct
5 Incorrect 279 ms 15084 KB Output is incorrect: {s, t} is wrong.
6 Halted 0 ms 0 KB -