oj.uz

Submission #294585

# Submission time Handle Problem Language Result Execution time Memory
294585 2020-09-09T06:24:22 Z Gurban Highway Tolls (IOI18_highway) C++17
100 / 100
 469 ms 11080 KB 
#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
#define pb push_back
#define ss second
#define ff first
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
typedef long double ld;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
const ll inf = 1e18;
const int mod = 1e9+7; //998244353;
const int maxn = 1e5+5;
const int Xg[4] = {1,0,-1,0}, Yg[4] = {0,1,0,-1};
ll modpw(ll a,ll e) {if(e==0)return 1;ll x=modpw(a*a%mod,e>>1);return e&1?x*a%mod:x;}

int M;
vi col,C,D;
ll init;
queue<pii>q;
int dis[maxn];
vector<pii> adj[maxn];

int bin(vi v){
	
	int l = 0,r = sz(v) - 1,md,jog=0;
	
	while(l <= r){
		md = (l+r)/2;
		
		for(int i = 0;i < M;i++) col[i]=0;
		for(int i = md;i < sz(v);i++)
			for(auto j : adj[v[i]]) col[j.ss]=1;

		ll now=ask(col);

		if(now != init) l=md+1,jog=md;
		else r=md-1;
	}
	return v[jog];
}

void find_pair(int N, vi U, vi V, int A, int B) {
	M = sz(U); col.resize(M);
	for(int i = 0;i < M;i++){adj[U[i]].pb({V[i],i});adj[V[i]].pb({U[i],i});}
	
	init = ask(col);

	int l = 0,r = M-1,md,jog=0;
	while(l <= r){
		md = (l+r)/2;
		for(int i = 0;i <= md;i++) col[i]=1;
		for(int i = md+1;i < M;i++) col[i]=0;

		ll now=ask(col);

		if(now != init) r=md-1,jog=md;
		else l=md+1;
	}

	q.push({U[jog],1}); dis[U[jog]]=1;
	q.push({V[jog],2}); dis[V[jog]]=2;

	while(!q.empty()){

		int x=q.front().ff;
		int y=q.front().ss;
		
		q.pop();
		
		if(y==1) C.pb(x);
		else D.pb(x);
		
		for(auto i : adj[x]){
			if(dis[i.ff]) continue;
			dis[i.ff]=y;
			q.push({i.ff,y});
		}
	}

	int ans=bin(C);
	int ans1=bin(D);

	answer(ans,ans1);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2784 KB Output is correct
2 Correct 19 ms 3328 KB Output is correct
3 Correct 249 ms 9132 KB Output is correct
4 Correct 212 ms 9152 KB Output is correct
5 Correct 242 ms 9172 KB Output is correct
6 Correct 177 ms 9124 KB Output is correct
7 Correct 235 ms 9148 KB Output is correct
8 Correct 370 ms 9160 KB Output is correct
9 Correct 319 ms 9224 KB Output is correct
10 Correct 263 ms 9148 KB Output is correct
11 Correct 323 ms 8368 KB Output is correct
12 Correct 297 ms 8468 KB Output is correct
13 Correct 281 ms 8512 KB Output is correct
14 Correct 273 ms 8540 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3328 KB Output is correct
2 Correct 28 ms 3960 KB Output is correct
3 Correct 44 ms 4544 KB Output is correct
4 Correct 136 ms 8372 KB Output is correct
5 Correct 138 ms 8304 KB Output is correct
6 Correct 145 ms 8432 KB Output is correct
7 Correct 166 ms 8688 KB Output is correct
8 Correct 129 ms 8432 KB Output is correct
9 Correct 132 ms 8416 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2792 KB Output is correct
2 Correct 18 ms 3328 KB Output is correct
3 Correct 207 ms 7712 KB Output is correct
4 Correct 316 ms 9288 KB Output is correct
5 Correct 320 ms 9132 KB Output is correct
6 Correct 335 ms 9152 KB Output is correct
7 Correct 366 ms 9284 KB Output is correct
8 Correct 343 ms 9120 KB Output is correct
9 Correct 320 ms 9084 KB Output is correct
10 Correct 290 ms 9300 KB Output is correct
11 Correct 295 ms 8540 KB Output is correct
12 Correct 208 ms 8692 KB Output is correct
13 Correct 305 ms 8612 KB Output is correct
14 Correct 337 ms 8388 KB Output is correct
15 Correct 310 ms 9156 KB Output is correct
16 Correct 388 ms 9288 KB Output is correct
17 Correct 259 ms 8592 KB Output is correct
18 Correct 278 ms 8524 KB Output is correct
19 Correct 323 ms 9160 KB Output is correct
20 Correct 312 ms 8688 KB Output is correct
21 Correct 157 ms 9972 KB Output is correct
22 Correct 143 ms 10008 KB Output is correct
23 Correct 167 ms 9344 KB Output is correct
24 Correct 160 ms 9280 KB Output is correct
25 Correct 171 ms 8784 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3448 KB Output is correct
2 Correct 23 ms 3448 KB Output is correct
3 Correct 211 ms 9564 KB Output is correct
4 Correct 306 ms 9952 KB Output is correct
5 Correct 436 ms 10960 KB Output is correct
6 Correct 423 ms 10804 KB Output is correct
7 Correct 451 ms 10756 KB Output is correct
8 Correct 347 ms 10984 KB Output is correct
9 Correct 212 ms 9004 KB Output is correct
10 Correct 196 ms 9208 KB Output is correct
11 Correct 250 ms 9616 KB Output is correct
12 Correct 342 ms 10332 KB Output is correct
13 Correct 400 ms 10736 KB Output is correct
14 Correct 424 ms 10920 KB Output is correct
15 Correct 418 ms 10856 KB Output is correct
16 Correct 224 ms 9656 KB Output is correct
17 Correct 208 ms 9832 KB Output is correct
18 Correct 247 ms 9972 KB Output is correct
19 Correct 144 ms 9832 KB Output is correct
20 Correct 250 ms 9956 KB Output is correct
21 Correct 409 ms 10948 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3596 KB Output is correct
2 Correct 40 ms 3452 KB Output is correct
3 Correct 371 ms 9648 KB Output is correct
4 Correct 373 ms 9688 KB Output is correct
5 Correct 381 ms 9948 KB Output is correct
6 Correct 378 ms 10708 KB Output is correct
7 Correct 348 ms 9568 KB Output is correct
8 Correct 365 ms 9736 KB Output is correct
9 Correct 384 ms 10076 KB Output is correct
10 Correct 439 ms 10844 KB Output is correct
11 Correct 430 ms 10960 KB Output is correct
12 Correct 422 ms 10780 KB Output is correct
13 Correct 235 ms 9852 KB Output is correct
14 Correct 202 ms 9208 KB Output is correct
15 Correct 229 ms 9720 KB Output is correct
16 Correct 206 ms 9212 KB Output is correct
17 Correct 219 ms 9720 KB Output is correct
18 Correct 181 ms 9276 KB Output is correct
19 Correct 385 ms 10452 KB Output is correct
20 Correct 390 ms 10684 KB Output is correct
21 Correct 453 ms 10752 KB Output is correct
22 Correct 427 ms 10812 KB Output is correct
23 Correct 431 ms 10856 KB Output is correct
24 Correct 405 ms 10840 KB Output is correct
25 Correct 462 ms 10912 KB Output is correct
26 Correct 411 ms 11024 KB Output is correct
27 Correct 198 ms 9928 KB Output is correct
28 Correct 259 ms 9828 KB Output is correct
29 Correct 287 ms 9960 KB Output is correct
30 Correct 142 ms 9700 KB Output is correct
31 Correct 231 ms 9864 KB Output is correct
32 Correct 260 ms 9732 KB Output is correct
33 Correct 229 ms 10036 KB Output is correct
34 Correct 288 ms 9816 KB Output is correct
35 Correct 282 ms 9848 KB Output is correct
36 Correct 318 ms 9864 KB Output is correct
37 Correct 300 ms 9996 KB Output is correct
38 Correct 158 ms 9800 KB Output is correct
39 Correct 460 ms 10904 KB Output is correct
40 Correct 469 ms 11080 KB Output is correct
41 Correct 304 ms 10976 KB Output is correct
42 Correct 441 ms 10928 KB Output is correct