oj.uz

Submission #415994

# Submission time Handle Problem Language Result Execution time Memory
415994 2021-06-01T19:25:39 Z mosiashvililuka Highway Tolls (IOI18_highway) C++14
90 / 100
 722 ms 19644 KB 
#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,A,B,x,bo[200009],lef,rig,mid,dis[200009],fx[200009],C,D;
deque <int> de;
vector <int> dep[200009];
long long K,X;
vector <pair <int, int> > v[200009];
vector <int> U,V,vv;
/*int ask(vector <int> va){
	int h=0,Ee;
	for(h=0; h<va.size(); h++){
		cout<<va[h]<<" ";
	}
	cout<<endl;
	cin>>Ee;
	return Ee;
}
void answer(int q, int w){
	cout<<"! "<<q<<" "<<w;
	exit(0);
}*/
void fun(){
	int h=0;
	for(h=0; h<b; h++) vv[h]=0;
	for(h=1; h<=a; h++){
		if(bo[h]==0) continue;
		for(vector <pair <int, int> >::iterator it=v[h].begin(); it!=v[h].end(); it++){
			vv[(*it).second]=1;
		}
	}
}
void rec(int q, int w){
	int h=0;
	if(q==w){
		x=q;
		return;
	}
	int mid=(q+w)/2;
	for(h=q; h<=mid; h++){
		bo[h]=1;
	}
	fun();
	X=ask(vv);
	if(K==X){
		rec(mid+1,w);
	}else{
		for(h=q; h<=mid; h++){
			bo[h]=0;
		}
		rec(q,mid);
	}
}
int povna(int q){
	while(de.size()) de.pop_back();
	for(i=1; i<=a; i++){
		dep[i].clear();
	}
	x=q;
	de.push_back(x);
	for(i=1; i<=a; i++) fx[i]=0;
	dis[x]=1;fx[x]=1;
	while(de.size()){
		c=de.front();
		de.pop_front();
		for(vector <pair <int, int> >::iterator it=v[c].begin(); it!=v[c].end(); it++){
			if(fx[(*it).first]==1) continue;
			dis[(*it).first]=dis[c]+1;
			fx[(*it).first]=1;
			de.push_back((*it).first);
		}
	}
	for(i=1; i<=a; i++){
		dep[dis[i]].push_back(i);
	}
	lef=1;rig=a+2;
	while(1){
		if(lef+1>=rig) break;
		mid=(lef+rig)/2;
		for(i=1; i<=a; i++) bo[i]=0;
		zx=a+1-mid;
//		cout<<"mid "<<mid<<"  "<<zx<<endl;
		for(j=a; j>=1; j--){
			for(jj=0; jj<dep[j].size(); jj++){
				if(zx==0) break;
				zx--;
				bo[dep[j][jj]]=1;
			}
			if(zx==0) break;
		}
		fun();
		X=ask(vv);
		if(K==X){
			rig=mid;
		}else{
			lef=mid;
		}
	}
	mid=lef;
	zx=a+1-mid;xc=0;
	for(j=a; j>=1; j--){
		for(jj=0; jj<dep[j].size(); jj++){
			if(zx==0) break;
			zx--;
			xc=dep[j][jj];
		}
		if(zx==0) break;
	}
	return xc;
}
void find_pair(int N, vector<int> UU, vector<int> VV, int AA, int BB) {
	a=N;b=UU.size();
	A=AA;B=BB;
	vv.resize(b);
	for(i=0; i<UU.size(); i++){
		U.push_back(UU[i]);V.push_back(VV[i]);
		U[i]++;V[i]++;
		v[U[i]].push_back(make_pair(V[i],i));
		v[V[i]].push_back(make_pair(U[i],i));
	}
	for(i=0; i<b; i++) vv[i]=0;
	K=ask(vv);
	rec(1,a);
//	cout<<"X "<<x<<endl;
	C=povna(x);
	D=povna(C);
	answer(C-1,D-1);
}

/*int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int N,M,S,T;
	cin>>N>>M>>A>>B>>S>>T;
	vector <int> UU,VV;
	for(i=1; i<=M; i++){
		cin>>c>>d;
		UU.push_back(c);VV.push_back(d);
	}
	find_pair(N,UU,VV,A,B);
	return 0;
}*/

Compilation message

highway.cpp: In function 'int povna(int)':
highway.cpp:84:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |    for(jj=0; jj<dep[j].size(); jj++){
      |              ~~^~~~~~~~~~~~~~
highway.cpp:102:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |   for(jj=0; jj<dep[j].size(); jj++){
      |             ~~^~~~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:115:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |  for(i=0; i<UU.size(); i++){
      |           ~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9672 KB Output is correct
2 Correct 7 ms 9672 KB Output is correct
3 Correct 10 ms 9700 KB Output is correct
4 Correct 8 ms 9636 KB Output is correct
5 Correct 9 ms 9748 KB Output is correct
6 Correct 7 ms 9672 KB Output is correct
7 Correct 6 ms 9704 KB Output is correct
8 Correct 7 ms 9672 KB Output is correct
9 Correct 7 ms 9604 KB Output is correct
10 Correct 6 ms 9708 KB Output is correct
11 Correct 8 ms 9672 KB Output is correct
12 Correct 7 ms 9672 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9672 KB Output is correct
2 Correct 26 ms 10440 KB Output is correct
3 Correct 451 ms 17288 KB Output is correct
4 Correct 250 ms 17228 KB Output is correct
5 Correct 298 ms 17312 KB Output is correct
6 Correct 203 ms 17248 KB Output is correct
7 Correct 266 ms 17464 KB Output is correct
8 Correct 363 ms 17568 KB Output is correct
9 Correct 399 ms 17680 KB Output is correct
10 Correct 363 ms 17268 KB Output is correct
11 Correct 459 ms 17344 KB Output is correct
12 Correct 393 ms 17356 KB Output is correct
13 Correct 457 ms 17040 KB Output is correct
14 Correct 376 ms 17360 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 10572 KB Output is correct
2 Correct 37 ms 11624 KB Output is correct
3 Correct 60 ms 12648 KB Output is correct
4 Correct 212 ms 17908 KB Output is correct
5 Correct 220 ms 17824 KB Output is correct
6 Correct 123 ms 18408 KB Output is correct
7 Correct 219 ms 18732 KB Output is correct
8 Correct 214 ms 18224 KB Output is correct
9 Correct 184 ms 18216 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9764 KB Output is correct
2 Correct 40 ms 10552 KB Output is correct
3 Correct 269 ms 15644 KB Output is correct
4 Correct 555 ms 17376 KB Output is correct
5 Correct 468 ms 17452 KB Output is correct
6 Correct 398 ms 17340 KB Output is correct
7 Correct 411 ms 17360 KB Output is correct
8 Correct 392 ms 17332 KB Output is correct
9 Correct 362 ms 17376 KB Output is correct
10 Correct 402 ms 17252 KB Output is correct
11 Correct 374 ms 17128 KB Output is correct
12 Correct 276 ms 17232 KB Output is correct
13 Correct 415 ms 17144 KB Output is correct
14 Correct 448 ms 17412 KB Output is correct
15 Correct 394 ms 17164 KB Output is correct
16 Correct 366 ms 17312 KB Output is correct
17 Correct 346 ms 17028 KB Output is correct
18 Correct 494 ms 17204 KB Output is correct
19 Correct 424 ms 17284 KB Output is correct
20 Correct 530 ms 17320 KB Output is correct
21 Correct 366 ms 18208 KB Output is correct
22 Correct 373 ms 17836 KB Output is correct
23 Correct 287 ms 17924 KB Output is correct
24 Correct 375 ms 18176 KB Output is correct
25 Correct 281 ms 18740 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 10560 KB Output is correct
2 Correct 42 ms 10636 KB Output is correct
3 Correct 310 ms 17724 KB Output is correct
4 Correct 428 ms 18240 KB Output is correct
5 Correct 538 ms 19544 KB Output is correct
6 Correct 505 ms 19452 KB Output is correct
7 Correct 439 ms 19608 KB Output is correct
8 Correct 434 ms 19392 KB Output is correct
9 Correct 372 ms 16772 KB Output is correct
10 Correct 457 ms 17468 KB Output is correct
11 Correct 474 ms 17792 KB Output is correct
12 Correct 369 ms 18748 KB Output is correct
13 Correct 507 ms 19260 KB Output is correct
14 Correct 425 ms 19504 KB Output is correct
15 Correct 505 ms 19372 KB Output is correct
16 Correct 377 ms 17832 KB Output is correct
17 Correct 298 ms 18152 KB Output is correct
18 Correct 338 ms 18320 KB Output is correct
19 Correct 377 ms 18296 KB Output is correct
20 Correct 360 ms 18428 KB Output is correct
21 Correct 700 ms 19552 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 10536 KB Output is correct
2 Correct 37 ms 10648 KB Output is correct
3 Partially correct 517 ms 18048 KB Output is partially correct
4 Correct 337 ms 18220 KB Output is correct
5 Correct 407 ms 18628 KB Output is correct
6 Partially correct 390 ms 19416 KB Output is partially correct
7 Partially correct 530 ms 18032 KB Output is partially correct
8 Correct 529 ms 17992 KB Output is correct
9 Correct 446 ms 18524 KB Output is correct
10 Correct 483 ms 19420 KB Output is correct
11 Correct 467 ms 19468 KB Output is correct
12 Correct 440 ms 19356 KB Output is correct
13 Correct 281 ms 17656 KB Output is correct
14 Correct 343 ms 17380 KB Output is correct
15 Correct 325 ms 17836 KB Output is correct
16 Correct 363 ms 17452 KB Output is correct
17 Correct 427 ms 17676 KB Output is correct
18 Correct 264 ms 17448 KB Output is correct
19 Correct 401 ms 18728 KB Output is correct
20 Correct 498 ms 19096 KB Output is correct
21 Correct 689 ms 19460 KB Output is correct
22 Correct 550 ms 19380 KB Output is correct
23 Correct 406 ms 19644 KB Output is correct
24 Correct 486 ms 19420 KB Output is correct
25 Correct 505 ms 19496 KB Output is correct
26 Correct 566 ms 19268 KB Output is correct
27 Partially correct 310 ms 18372 KB Output is partially correct
28 Partially correct 364 ms 17884 KB Output is partially correct
29 Partially correct 429 ms 18588 KB Output is partially correct
30 Correct 306 ms 18372 KB Output is correct
31 Partially correct 225 ms 18332 KB Output is partially correct
32 Partially correct 303 ms 18384 KB Output is partially correct
33 Partially correct 235 ms 18712 KB Output is partially correct
34 Partially correct 286 ms 17900 KB Output is partially correct
35 Partially correct 332 ms 18228 KB Output is partially correct
36 Correct 390 ms 18136 KB Output is correct
37 Correct 312 ms 18392 KB Output is correct
38 Correct 402 ms 18352 KB Output is correct
39 Partially correct 722 ms 19504 KB Output is partially correct
40 Partially correct 503 ms 19548 KB Output is partially correct
41 Correct 416 ms 19624 KB Output is correct
42 Correct 662 ms 19628 KB Output is correct