oj.uz

답안 #399118

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
399118 2021-05-05T10:22:42 Z kshitij_sodani 통행료 (IOI18_highway) C++14
100 / 100
 678 ms 17848 KB 
//#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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