oj.uz

Submission #123901

# Submission time Handle Problem Language Result Execution time Memory
123901 2019-07-02T09:15:22 Z nvmdava Highway Tolls (IOI18_highway) C++17
100 / 100
 411 ms 10588 KB 
#include "highway.h"
#define pb push_back
#include <bits/stdc++.h>
using namespace std;

vector<int> adj[100005];
vector<int> path;
long long def;
vector<int> w;
int v[3], p[100005], cat[100005];
vector<int> com[3];
int solve(vector<int>& ve){
	reverse(ve.begin(), ve.end());
	int l = 0, r = ve.size() - 1;
	while(l != r){
		int m = (l + r) >> 1;
		for(int i = 0; i <= m; i++)
			w[p[ve[i]]] = 1;
		if(ask(w) > def) r = m;
		else l = m + 1;
		for(int i = 0; i <= m; i++)
			w[p[ve[i]]] = 0;
	}
	return ve[l];
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
	int m = U.size();
	for(int i = 0; i < m; i++){
		adj[U[i]].pb(i);
		adj[V[i]].pb(i);
		path.push_back(V[i] + U[i]);
	}
	w = vector<int>(m, 0);
	def = ask(w);	
	int l = 0, r = m - 1;
	while(l != r){
		int mm = (l + r) >> 1;
		for(int i = 0; i <= mm; i++)
			w[i] = 1;
		if(ask(w) > def) r = mm;
		else l = mm + 1;
		for(int i = 0; i <= mm; i++)
			w[i] = 0;
	}
	
	queue<pair<int, int> > q;
	q.push({V[l], 1});
	q.push({U[l], 2});
	cat[V[l]] = 1;
	p[V[l]] = l;
	p[U[l]] = l;
	cat[U[l]] = 2;
	com[1].pb(V[l]);
	com[2].pb(U[l]);
	while(!q.empty()){
		int u = q.front().first, t = q.front().second;
		q.pop();
		for(int x : adj[u]){
			int e = path[x] - u; 
			if(cat[e]) continue;
			cat[e] = t;
			com[t].pb(e);
			p[e] = x;
			q.push({e, t});
		}
	}
	for(int i = 0; i < m; i++)
		w[i] = 1;
	for(int i = 0; i < N; i++)
		w[p[i]] = 0;
	answer(solve(com[1]), solve(com[2]));
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2752 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 4 ms 2708 KB Output is correct
6 Correct 4 ms 2760 KB Output is correct
7 Correct 4 ms 2552 KB Output is correct
8 Correct 4 ms 2552 KB Output is correct
9 Correct 4 ms 2552 KB Output is correct
10 Correct 4 ms 2552 KB Output is correct
11 Correct 4 ms 2672 KB Output is correct
12 Correct 4 ms 2552 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2680 KB Output is correct
2 Correct 24 ms 3384 KB Output is correct
3 Correct 229 ms 9128 KB Output is correct
4 Correct 237 ms 9128 KB Output is correct
5 Correct 238 ms 9124 KB Output is correct
6 Correct 216 ms 9116 KB Output is correct
7 Correct 252 ms 9120 KB Output is correct
8 Correct 252 ms 9248 KB Output is correct
9 Correct 262 ms 9116 KB Output is correct
10 Correct 236 ms 9252 KB Output is correct
11 Correct 262 ms 8980 KB Output is correct
12 Correct 284 ms 9164 KB Output is correct
13 Correct 273 ms 9040 KB Output is correct
14 Correct 250 ms 9028 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3380 KB Output is correct
2 Correct 44 ms 4088 KB Output is correct
3 Correct 67 ms 4828 KB Output is correct
4 Correct 153 ms 9052 KB Output is correct
5 Correct 163 ms 9000 KB Output is correct
6 Correct 170 ms 9244 KB Output is correct
7 Correct 186 ms 8932 KB Output is correct
8 Correct 171 ms 8992 KB Output is correct
9 Correct 201 ms 9264 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2680 KB Output is correct
2 Correct 24 ms 3428 KB Output is correct
3 Correct 199 ms 7888 KB Output is correct
4 Correct 242 ms 9132 KB Output is correct
5 Correct 257 ms 9124 KB Output is correct
6 Correct 271 ms 9136 KB Output is correct
7 Correct 238 ms 9200 KB Output is correct
8 Correct 244 ms 9128 KB Output is correct
9 Correct 238 ms 9132 KB Output is correct
10 Correct 252 ms 9132 KB Output is correct
11 Correct 247 ms 9028 KB Output is correct
12 Correct 222 ms 9284 KB Output is correct
13 Correct 268 ms 9280 KB Output is correct
14 Correct 270 ms 8928 KB Output is correct
15 Correct 251 ms 9128 KB Output is correct
16 Correct 236 ms 9144 KB Output is correct
17 Correct 249 ms 9036 KB Output is correct
18 Correct 243 ms 9024 KB Output is correct
19 Correct 258 ms 9140 KB Output is correct
20 Correct 271 ms 9048 KB Output is correct
21 Correct 193 ms 9836 KB Output is correct
22 Correct 185 ms 9832 KB Output is correct
23 Correct 207 ms 9492 KB Output is correct
24 Correct 201 ms 9400 KB Output is correct
25 Correct 221 ms 9212 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3384 KB Output is correct
2 Correct 31 ms 3448 KB Output is correct
3 Correct 189 ms 9584 KB Output is correct
4 Correct 298 ms 9728 KB Output is correct
5 Correct 342 ms 10500 KB Output is correct
6 Correct 344 ms 10500 KB Output is correct
7 Correct 341 ms 10440 KB Output is correct
8 Correct 338 ms 10408 KB Output is correct
9 Correct 250 ms 7972 KB Output is correct
10 Correct 243 ms 8352 KB Output is correct
11 Correct 215 ms 8648 KB Output is correct
12 Correct 316 ms 9868 KB Output is correct
13 Correct 352 ms 10048 KB Output is correct
14 Correct 331 ms 10164 KB Output is correct
15 Correct 342 ms 10068 KB Output is correct
16 Correct 264 ms 8800 KB Output is correct
17 Correct 182 ms 10056 KB Output is correct
18 Correct 240 ms 9988 KB Output is correct
19 Correct 186 ms 9932 KB Output is correct
20 Correct 249 ms 10016 KB Output is correct
21 Correct 347 ms 10420 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 3424 KB Output is correct
2 Correct 25 ms 3472 KB Output is correct
3 Correct 297 ms 9516 KB Output is correct
4 Correct 276 ms 9780 KB Output is correct
5 Correct 313 ms 9932 KB Output is correct
6 Correct 351 ms 10548 KB Output is correct
7 Correct 269 ms 9552 KB Output is correct
8 Correct 280 ms 9704 KB Output is correct
9 Correct 310 ms 9856 KB Output is correct
10 Correct 353 ms 10588 KB Output is correct
11 Correct 411 ms 10460 KB Output is correct
12 Correct 360 ms 10500 KB Output is correct
13 Correct 267 ms 8568 KB Output is correct
14 Correct 248 ms 8288 KB Output is correct
15 Correct 242 ms 8632 KB Output is correct
16 Correct 235 ms 8328 KB Output is correct
17 Correct 248 ms 8760 KB Output is correct
18 Correct 230 ms 8300 KB Output is correct
19 Correct 338 ms 9792 KB Output is correct
20 Correct 327 ms 9984 KB Output is correct
21 Correct 350 ms 10092 KB Output is correct
22 Correct 367 ms 10320 KB Output is correct
23 Correct 370 ms 10304 KB Output is correct
24 Correct 336 ms 10232 KB Output is correct
25 Correct 362 ms 10320 KB Output is correct
26 Correct 326 ms 10368 KB Output is correct
27 Correct 203 ms 10004 KB Output is correct
28 Correct 245 ms 9948 KB Output is correct
29 Correct 241 ms 10124 KB Output is correct
30 Correct 211 ms 9928 KB Output is correct
31 Correct 234 ms 10084 KB Output is correct
32 Correct 227 ms 9932 KB Output is correct
33 Correct 209 ms 10096 KB Output is correct
34 Correct 219 ms 10088 KB Output is correct
35 Correct 259 ms 10040 KB Output is correct
36 Correct 249 ms 9896 KB Output is correct
37 Correct 249 ms 10164 KB Output is correct
38 Correct 210 ms 9908 KB Output is correct
39 Correct 323 ms 10348 KB Output is correct
40 Correct 298 ms 10312 KB Output is correct
41 Correct 292 ms 10184 KB Output is correct
42 Correct 331 ms 10176 KB Output is correct