oj.uz

Submission #399174

# Submission time Handle Problem Language Result Execution time Memory
399174 2021-05-05T11:32:00 Z kshitij_sodani Highway Tolls (IOI18_highway) C++14
100 / 100
 465 ms 22496 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<llo> adj2[100001];

vector<pair<llo,llo>> lev[100001];
llo dist[100001];
llo ba[100001];
llo vis[100001];
llo vis2[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 dfs2(int no){
	vis2[no]=1;
	for(auto  j:adj2[no]){
		if(vis2[j]==0){
			dfs2(j);
		}
	}
}
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){
				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++){
		if(dist[i]==-1){
			vis2[i]=2;
		}
	}
	for(int i=0;i<n;i++){
		for(auto j:adj[i]){
			if(dist[i]==-1 or dist[j.a]==-1){
				continue;
			}

			if(dist[j.a]==dist[i]-1 and dist[j.a]>0){
				adj2[j.a].pb(i);
			}
		}
	}
	dfs2(no.b);
	for(int i=0;i<n;i++){
		if(vis2[i]==0){
			tt.pb({dist[i],i});
		}
	}
	/*cout<<no.a<<"::"<<no.b<<endl;
	for(int i=0;i<n;i++){
		cout<<vis2[i]<<":";
	}
	cout<<endl;*/
	sort(tt.begin(),tt.end());
	reverse(tt.begin(),tt.end());
	low=0;
	for(int j=19;j>=0;j--){
		if(low+(1<<j)<=tt.size()){
			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 and dist[k.a]!=-1){
						cur2[k.b]=1;
					}
				}
			}
			if(ask(cur2)==ans){
				low+=(1<<j);
			}
		}
	}
	//cout<<low<<"::"<<endl;

	int xx=no.a;
	if(low<tt.size()){
		xx=tt[low].b;
	}
	tt.clear();
	for(int i=0;i<n;i++){
		if(vis2[i]==1){
			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)<=tt.size()){
			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 and dist[k.a]!=-1){
						cur2[k.b]=1;
					}
				}
			}
			if(ask(cur2)==ans){
				low+=(1<<j);
			}
		}
	}
	//cout<<low<<"::"<<endl;


/*	llo zz=xx;
	while(zz>=0){
		vis[zz]=1;
		zz=ba[zz];
	}
	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++){
				if(vis[tt[i].b]==1){
				//	cout<<tt[i].b<<"???"<<endl;
					continue;
				}

				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);
			}
		}
	}*/


//	cout<<low<<endl;
	//cout<<tt[low].b<<",,"<<endl;
	/*if(low==tt.size()){
		answer(xx,no.a);
		return;
	}*/
	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);*/



}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:123:16: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long long int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |   if(low+(1<<j)<=tt.size()){
      |      ~~~~~~~~~~^~~~~~~~~~~
highway.cpp:141:8: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long long int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |  if(low<tt.size()){
      |     ~~~^~~~~~~~~~
highway.cpp:154:16: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long long int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |   if(low+(1<<j)<=tt.size()){
      |      ~~~~~~~~~~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7368 KB Output is correct
2 Correct 5 ms 7304 KB Output is correct
3 Correct 5 ms 7240 KB Output is correct
4 Correct 5 ms 7348 KB Output is correct
5 Correct 6 ms 7352 KB Output is correct
6 Correct 5 ms 7368 KB Output is correct
7 Correct 5 ms 7328 KB Output is correct
8 Correct 6 ms 7360 KB Output is correct
9 Correct 5 ms 7352 KB Output is correct
10 Correct 5 ms 7240 KB Output is correct
11 Correct 5 ms 7368 KB Output is correct
12 Correct 5 ms 7368 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7368 KB Output is correct
2 Correct 23 ms 8648 KB Output is correct
3 Correct 222 ms 18700 KB Output is correct
4 Correct 214 ms 18804 KB Output is correct
5 Correct 259 ms 18964 KB Output is correct
6 Correct 192 ms 17628 KB Output is correct
7 Correct 212 ms 17416 KB Output is correct
8 Correct 267 ms 19056 KB Output is correct
9 Correct 238 ms 17488 KB Output is correct
10 Correct 230 ms 18088 KB Output is correct
11 Correct 143 ms 16816 KB Output is correct
12 Correct 321 ms 19508 KB Output is correct
13 Correct 346 ms 20612 KB Output is correct
14 Correct 268 ms 20088 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 8904 KB Output is correct
2 Correct 38 ms 10420 KB Output is correct
3 Correct 36 ms 10448 KB Output is correct
4 Correct 117 ms 19888 KB Output is correct
5 Correct 151 ms 19948 KB Output is correct
6 Correct 159 ms 21472 KB Output is correct
7 Correct 131 ms 16280 KB Output is correct
8 Correct 127 ms 20428 KB Output is correct
9 Correct 111 ms 17700 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7368 KB Output is correct
2 Correct 23 ms 8488 KB Output is correct
3 Correct 224 ms 16420 KB Output is correct
4 Correct 276 ms 18564 KB Output is correct
5 Correct 120 ms 16244 KB Output is correct
6 Correct 163 ms 16100 KB Output is correct
7 Correct 204 ms 17452 KB Output is correct
8 Correct 166 ms 16452 KB Output is correct
9 Correct 259 ms 18700 KB Output is correct
10 Correct 257 ms 17804 KB Output is correct
11 Correct 296 ms 19828 KB Output is correct
12 Correct 234 ms 19796 KB Output is correct
13 Correct 290 ms 18716 KB Output is correct
14 Correct 159 ms 17064 KB Output is correct
15 Correct 121 ms 16256 KB Output is correct
16 Correct 119 ms 16208 KB Output is correct
17 Correct 222 ms 19644 KB Output is correct
18 Correct 337 ms 20136 KB Output is correct
19 Correct 113 ms 16212 KB Output is correct
20 Correct 117 ms 16316 KB Output is correct
21 Correct 176 ms 16928 KB Output is correct
22 Correct 168 ms 16316 KB Output is correct
23 Correct 198 ms 17812 KB Output is correct
24 Correct 191 ms 18076 KB Output is correct
25 Correct 229 ms 19748 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 8556 KB Output is correct
2 Correct 30 ms 8716 KB Output is correct
3 Correct 287 ms 19688 KB Output is correct
4 Correct 361 ms 19696 KB Output is correct
5 Correct 371 ms 21344 KB Output is correct
6 Correct 397 ms 21476 KB Output is correct
7 Correct 421 ms 21272 KB Output is correct
8 Correct 309 ms 21632 KB Output is correct
9 Correct 205 ms 16064 KB Output is correct
10 Correct 243 ms 18608 KB Output is correct
11 Correct 240 ms 18380 KB Output is correct
12 Correct 379 ms 20520 KB Output is correct
13 Correct 338 ms 20908 KB Output is correct
14 Correct 446 ms 21648 KB Output is correct
15 Correct 349 ms 22172 KB Output is correct
16 Correct 225 ms 19268 KB Output is correct
17 Correct 151 ms 17180 KB Output is correct
18 Correct 128 ms 16740 KB Output is correct
19 Correct 150 ms 18228 KB Output is correct
20 Correct 139 ms 17128 KB Output is correct
21 Correct 361 ms 22496 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 8544 KB Output is correct
2 Correct 27 ms 8752 KB Output is correct
3 Correct 371 ms 19332 KB Output is correct
4 Correct 342 ms 19412 KB Output is correct
5 Correct 373 ms 19988 KB Output is correct
6 Correct 345 ms 21740 KB Output is correct
7 Correct 345 ms 19776 KB Output is correct
8 Correct 331 ms 20320 KB Output is correct
9 Correct 356 ms 19972 KB Output is correct
10 Correct 417 ms 21300 KB Output is correct
11 Correct 349 ms 21348 KB Output is correct
12 Correct 363 ms 21340 KB Output is correct
13 Correct 148 ms 17324 KB Output is correct
14 Correct 149 ms 17180 KB Output is correct
15 Correct 231 ms 19848 KB Output is correct
16 Correct 179 ms 18304 KB Output is correct
17 Correct 255 ms 18912 KB Output is correct
18 Correct 239 ms 19112 KB Output is correct
19 Correct 331 ms 20524 KB Output is correct
20 Correct 359 ms 21632 KB Output is correct
21 Correct 465 ms 21636 KB Output is correct
22 Correct 379 ms 21496 KB Output is correct
23 Correct 424 ms 21600 KB Output is correct
24 Correct 400 ms 21608 KB Output is correct
25 Correct 412 ms 22216 KB Output is correct
26 Correct 418 ms 22132 KB Output is correct
27 Correct 172 ms 16964 KB Output is correct
28 Correct 203 ms 17952 KB Output is correct
29 Correct 201 ms 18920 KB Output is correct
30 Correct 212 ms 18352 KB Output is correct
31 Correct 215 ms 17944 KB Output is correct
32 Correct 179 ms 18012 KB Output is correct
33 Correct 209 ms 18864 KB Output is correct
34 Correct 194 ms 17568 KB Output is correct
35 Correct 181 ms 17592 KB Output is correct
36 Correct 209 ms 17888 KB Output is correct
37 Correct 193 ms 18404 KB Output is correct
38 Correct 201 ms 18440 KB Output is correct
39 Correct 389 ms 22384 KB Output is correct
40 Correct 435 ms 22104 KB Output is correct
41 Correct 321 ms 22236 KB Output is correct
42 Correct 457 ms 21572 KB Output is correct