Submission #399118

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
399118	2021-05-05T10:22:42 Z	kshitij_sodani	Highway Tolls (IOI18_highway)	C++14	100 / 100	678 ms	17848 KB

highway

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'

#include "highway.h"

vector<int> cur;
vector<pair<llo,llo>> adj[100001];
vector<pair<llo,llo>> lev[100001];
llo dist[100001];
llo ba[100001];
llo vis[100001];
void dfs(llo no,llo par=-1,llo levv=0,llo la=-1){
	lev[levv].pb({no,la});
	for(auto j:adj[no]){
		if(j.a!=par){
			dfs(j.a,no,levv+1,j.b);
		}
	}
}
void find_pair(int n, std::vector<int> uu, std::vector<int> vv, int aa, int bb) {
	int m=uu.size();
	for(int i=0;i<m;i++){
		cur.pb(0);
	}
	llo ans=ask(cur);
	for(int i=0;i<m;i++){
		adj[uu[i]].pb({vv[i],i});
		adj[vv[i]].pb({uu[i],i});
	}
	llo low=0;
	for(int j=19;j>=0;j--){
		if(low+(1LL<<j)<=m){
			vector<int> cur2=cur;
			for(int i=0;i<low+(1<<j);i++){
				cur2[i]=1;
			}
			if(ask(cur2)==ans){
				low+=(1<<j);
			}
		}
	}
	for(int i=0;i<low;i++){
		if((aa==1 and bb==2)){
			cur[i]=1;
		}
	}

	//return;
	pair<int,int> no={uu[low],vv[low]};
	for(int i=0;i<n;i++){
		dist[i]=-1;
		ba[i]=-1;
	}
	queue<int> ss;
	ss.push(no.a);
	dist[no.a]=0;
	while(ss.size()){
		int cot=ss.front();
		ss.pop();
		for(auto j:adj[cot]){
			if(j.b<low and (aa==1 and bb==2)){
				continue;
			}
			if(dist[j.a]==-1){

				dist[j.a]=dist[cot]+1;
				ba[j.a]=cot;
				ss.push(j.a);
			}
		}
	}
	vector<pair<int,int>> tt;
	for(int i=0;i<n;i++){
		tt.pb({dist[i],i});
	}
	sort(tt.begin(),tt.end());
	reverse(tt.begin(),tt.end());
	low=0;
	for(int j=19;j>=0;j--){
		if(low+(1<<j)<=n){
			vector<int> cur2=cur;
			for(int i=0;i<low+(1<<j);i++){
				int x=tt[i].b;
				for(auto k:adj[x]){
					if(dist[k.a]==dist[x]-1){
						cur2[k.b]=1;
					}
				}
			}
			if(ask(cur2)==ans){
				low+=(1<<j);
			}
		}
	}
	int xx=tt[low].b;
	//cout<<no.a<<":"<<no.b<<endl;
	//cout<<xx<<":"<<endl;
	if(dist[xx]==(ans/(llo)aa)){
		answer(xx,no.a);
		return;
	}
	llo zz=xx;
	while(zz>=0){
		vis[zz]=1;
		//cout<<zz<<".";
		zz=ba[zz];
	}
	//cout<<endl;
	low=0;
	/*for(auto j:tt){
		cout<<j.a<<"<<"<<j.b<<endl;
	}
	cout<<endl<<endl;
	for(int i=0;i<n;i++){
		cout<<dist[i]<<"<";
	}
	cout<<endl;*/
	for(int j=19;j>=0;j--){
		if(low+(1<<j)<=n){
			vector<int> cur2=cur;
			for(int i=0;i<low+(1<<j);i++){
				if(vis[tt[i].b]==1){
				//	cout<<tt[i].b<<"???"<<endl;
					continue;
				}

				int x=tt[i].b;
				for(auto k:adj[x]){
					/*if(tt[i].b==3){
						cout<<k.a<<"{{"<<k.b<<endl;
						cout<<dist[k.a]<<"}}"<<dist[x]<<endl;
					}*/
					if(dist[k.a]==dist[x]-1){
						cur2[k.b]=1;
					/*	if(tt[i].b==3){
							cout<<k.b<<"!!"<<endl;
						}*/
					}
				}
			}
			if(ask(cur2)==ans){
				/*cout<<low+(1<<j)<<":::"<<endl;
				for(auto ii:cur2){
					cout<<ii;
				}
				cout<<endl;
				cout<<ask(cur2)<<endl;*/
				low+=(1<<j);
			}
		}
	}
//	cout<<low<<endl;
	//cout<<tt[low].b<<",,"<<endl;
	answer(xx,tt[low].b);





/*	int l=0;
	int r=m-1;
	while(l<r){
		int mid=(l+r)/2;
		vector<int> cur2=cur;
		for(int i=l;i<=mid;i++){
			cur2[i]=1;
		}
		if(ask(cur2)==ans){
			l=mid+1;
		}
		else{
			r=mid;
		}
	}
	//return;
	pair<int,int> no={uu[l],vv[l]};
	for(int i=0;i<=n;i++){
		lev[i].clear();
	}
	dfs(no.a,no.b,0,l);
	vector<pair<llo,llo>> ord;
	for(int i=n;i>=0;i--){
		for(auto j:lev[i]){
			ord.pb(j);
		}
	}
	llo low=0;
	for(int j=19;j>=0;j--){
		if(low+(1<<j)<=ord.size()){
			vector<int> cur2=cur;
			for(int i=0;i<low+(1<<j);i++){
				cur2[ord[i].b]=1;
			}
			if(ask(cur2)==ans){
				low+=(1<<j);
			}
		}
	}
	int xx=ord[low].a;
	ord.clear();
	for(int i=0;i<=n;i++){
		lev[i].clear();
	}
	dfs(no.b,no.a,0,l);
	for(int i=n;i>=0;i--){
		for(auto j:lev[i]){
			ord.pb(j);
		}
	}
	low=0;
	for(int j=19;j>=0;j--){
		if(low+(1<<j)<=ord.size()){
			vector<int> cur2=cur;
			for(int i=0;i<low+(1<<j);i++){
				cur2[ord[i].b]=1;
			}
			if(ask(cur2)==ans){
				low+=(1<<j);
			}
		}
	}
	int yy=ord[low].a;
	answer(xx,yy);*/



}

Subtask #1

5.0 / 5.0

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

Subtask #2

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	5064 KB	Output is correct
2	Correct	28 ms	6008 KB	Output is correct
3	Correct	382 ms	14300 KB	Output is correct
4	Correct	376 ms	14336 KB	Output is correct
5	Correct	356 ms	14324 KB	Output is correct
6	Correct	164 ms	14268 KB	Output is correct
7	Correct	347 ms	14272 KB	Output is correct
8	Correct	390 ms	14388 KB	Output is correct
9	Correct	352 ms	14324 KB	Output is correct
10	Correct	379 ms	14268 KB	Output is correct
11	Correct	195 ms	14864 KB	Output is correct
12	Correct	472 ms	14848 KB	Output is correct
13	Correct	438 ms	15024 KB	Output is correct
14	Correct	459 ms	14940 KB	Output is correct

Subtask #3

6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	5964 KB	Output is correct
2	Correct	28 ms	6944 KB	Output is correct
3	Correct	40 ms	7816 KB	Output is correct
4	Correct	128 ms	13928 KB	Output is correct
5	Correct	165 ms	13892 KB	Output is correct
6	Correct	155 ms	13828 KB	Output is correct
7	Correct	154 ms	13872 KB	Output is correct
8	Correct	155 ms	13828 KB	Output is correct
9	Correct	118 ms	13908 KB	Output is correct

Subtask #4

33.0 / 33.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	5064 KB	Output is correct
2	Correct	25 ms	6000 KB	Output is correct
3	Correct	184 ms	12236 KB	Output is correct
4	Correct	371 ms	14300 KB	Output is correct
5	Correct	429 ms	14328 KB	Output is correct
6	Correct	297 ms	14268 KB	Output is correct
7	Correct	292 ms	14320 KB	Output is correct
8	Correct	412 ms	14264 KB	Output is correct
9	Correct	375 ms	14396 KB	Output is correct
10	Correct	393 ms	14400 KB	Output is correct
11	Correct	449 ms	15004 KB	Output is correct
12	Correct	386 ms	14960 KB	Output is correct
13	Correct	393 ms	14960 KB	Output is correct
14	Correct	368 ms	14876 KB	Output is correct
15	Correct	179 ms	14252 KB	Output is correct
16	Correct	270 ms	14288 KB	Output is correct
17	Correct	404 ms	14928 KB	Output is correct
18	Correct	478 ms	14992 KB	Output is correct
19	Correct	401 ms	14340 KB	Output is correct
20	Correct	418 ms	14852 KB	Output is correct
21	Correct	161 ms	14292 KB	Output is correct
22	Correct	239 ms	14280 KB	Output is correct
23	Correct	189 ms	14904 KB	Output is correct
24	Correct	202 ms	14884 KB	Output is correct
25	Correct	263 ms	14832 KB	Output is correct

Subtask #5

18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	29 ms	6268 KB	Output is correct
2	Correct	34 ms	6328 KB	Output is correct
3	Correct	360 ms	15052 KB	Output is correct
4	Correct	431 ms	15820 KB	Output is correct
5	Correct	516 ms	17220 KB	Output is correct
6	Correct	520 ms	17224 KB	Output is correct
7	Correct	519 ms	17248 KB	Output is correct
8	Correct	507 ms	17236 KB	Output is correct
9	Correct	229 ms	13972 KB	Output is correct
10	Correct	192 ms	15296 KB	Output is correct
11	Correct	276 ms	15664 KB	Output is correct
12	Correct	281 ms	16852 KB	Output is correct
13	Correct	435 ms	17116 KB	Output is correct
14	Correct	484 ms	17216 KB	Output is correct
15	Correct	529 ms	17376 KB	Output is correct
16	Correct	359 ms	15912 KB	Output is correct
17	Correct	234 ms	14148 KB	Output is correct
18	Correct	187 ms	14592 KB	Output is correct
19	Correct	233 ms	14244 KB	Output is correct
20	Correct	209 ms	14248 KB	Output is correct
21	Correct	597 ms	17684 KB	Output is correct

Subtask #6

31.0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	6160 KB	Output is correct
2	Correct	25 ms	6172 KB	Output is correct
3	Correct	373 ms	15120 KB	Output is correct
4	Correct	476 ms	15400 KB	Output is correct
5	Correct	471 ms	15772 KB	Output is correct
6	Correct	418 ms	17256 KB	Output is correct
7	Correct	408 ms	15160 KB	Output is correct
8	Correct	432 ms	15416 KB	Output is correct
9	Correct	453 ms	15848 KB	Output is correct
10	Correct	480 ms	17256 KB	Output is correct
11	Correct	482 ms	17184 KB	Output is correct
12	Correct	449 ms	17220 KB	Output is correct
13	Correct	227 ms	15556 KB	Output is correct
14	Correct	233 ms	15120 KB	Output is correct
15	Correct	190 ms	15640 KB	Output is correct
16	Correct	233 ms	15228 KB	Output is correct
17	Correct	175 ms	15688 KB	Output is correct
18	Correct	179 ms	15120 KB	Output is correct
19	Correct	420 ms	16980 KB	Output is correct
20	Correct	490 ms	17280 KB	Output is correct
21	Correct	517 ms	17180 KB	Output is correct
22	Correct	492 ms	17228 KB	Output is correct
23	Correct	470 ms	17312 KB	Output is correct
24	Correct	428 ms	17232 KB	Output is correct
25	Correct	524 ms	17232 KB	Output is correct
26	Correct	532 ms	17240 KB	Output is correct
27	Correct	232 ms	14344 KB	Output is correct
28	Correct	234 ms	14160 KB	Output is correct
29	Correct	243 ms	14808 KB	Output is correct
30	Correct	260 ms	14304 KB	Output is correct
31	Correct	221 ms	14272 KB	Output is correct
32	Correct	237 ms	14192 KB	Output is correct
33	Correct	301 ms	14776 KB	Output is correct
34	Correct	236 ms	14504 KB	Output is correct
35	Correct	254 ms	14320 KB	Output is correct
36	Correct	232 ms	14152 KB	Output is correct
37	Correct	278 ms	14740 KB	Output is correct
38	Correct	157 ms	14396 KB	Output is correct
39	Correct	586 ms	17848 KB	Output is correct
40	Correct	597 ms	17836 KB	Output is correct
41	Correct	451 ms	17836 KB	Output is correct
42	Correct	678 ms	17808 KB	Output is correct