oj.uz

Submission #75237

# Submission time Handle Problem Language Result Execution time Memory
75237 2018-09-08T18:11:54 Z ainta Highway Tolls (IOI18_highway) C++17
100 / 100
 375 ms 11420 KB 
#include "highway.h"
#include <cstdio>
#include <algorithm>
#define N_ 151000
using namespace std;
int n, m, Q[N_], head, tail, par[N_], vis[N_], pN[N_], vv[N_];
vector<int>T, E[N_];

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	int i;
	n = N;
	m = U.size();
	T.resize(m);
	for (i = 0; i < m; i++) {
		T[i] = 0;
		E[U[i]].push_back(V[i]);
		E[V[i]].push_back(U[i]);
	}
	long long L = ask(T);
	int b = 0, e = n - 2, mid, r = n - 1;
	while (b <= e) {
		mid = (b + e) >> 1;
		if (e - b > 60000)mid = 60000;
		for (i = 0; i < m; i++) {
			if (U[i] > mid || V[i] > mid)T[i] = 1;
			else T[i] = 0;
		}
		if (ask(T) == L)r = mid, e = mid - 1;
		else b = mid + 1;
	}
	int root = r;
	Q[++tail] = root, vis[root] = 1;
	par[root] = -1;
	while (head < tail) {
		int x = Q[++head];
		for (auto &y : E[x]) {
			if (!vis[y]) {
				vis[y] = 1;
				Q[++tail] = y;
				par[y] = x;
			}
		}
	}
	for (i = 0; i < m; i++) {
		if (par[U[i]] == V[i])pN[U[i]] = i;
		if (par[V[i]] == U[i])pN[V[i]] = i;
	}
	b = 1, e = tail - 1, r = tail;
	while (b <= e) {
		mid = (b + e) >> 1;
		if (e - b > 60000)mid = 60000;
		for (i = 0; i < m; i++)T[i] = 1;
		for (i = 2; i <= mid; i++) T[pN[Q[i]]] = 0;
		if (ask(T) == L)r = mid, e = mid - 1;
		else b = mid + 1;
	}
	int ed = Q[r];
	int tp = ed;
	while (tp != root) {
		vv[pN[tp]] = 1;
		tp = par[tp];
	}
	b = 1, e = r - 1;
	while (b <= e) {
		mid = (b + e) >> 1;
		for (i = 0; i < m; i++) {
			if(!vv[i])T[i] = 1;
			else T[i] = 0;
		}
		for (i = 2; i <= mid; i++) T[pN[Q[i]]] = 0;
		if (ask(T) == L)r = mid, e = mid - 1;
		else b = mid + 1;
	}
	int st = Q[r];
	answer(st, ed);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3832 KB Output is correct
2 Correct 5 ms 3864 KB Output is correct
3 Correct 5 ms 3860 KB Output is correct
4 Correct 5 ms 3864 KB Output is correct
5 Correct 5 ms 3868 KB Output is correct
6 Correct 5 ms 3832 KB Output is correct
7 Correct 5 ms 3880 KB Output is correct
8 Correct 5 ms 3868 KB Output is correct
9 Correct 5 ms 3832 KB Output is correct
10 Correct 5 ms 3960 KB Output is correct
11 Correct 5 ms 3868 KB Output is correct
12 Correct 6 ms 3880 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3908 KB Output is correct
2 Correct 27 ms 4516 KB Output is correct
3 Correct 219 ms 10044 KB Output is correct
4 Correct 233 ms 10044 KB Output is correct
5 Correct 290 ms 10048 KB Output is correct
6 Correct 263 ms 10064 KB Output is correct
7 Correct 222 ms 10024 KB Output is correct
8 Correct 214 ms 10012 KB Output is correct
9 Correct 192 ms 10028 KB Output is correct
10 Correct 219 ms 10080 KB Output is correct
11 Correct 231 ms 10232 KB Output is correct
12 Correct 260 ms 10324 KB Output is correct
13 Correct 227 ms 10244 KB Output is correct
14 Correct 236 ms 10240 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 4548 KB Output is correct
2 Correct 43 ms 5224 KB Output is correct
3 Correct 47 ms 5880 KB Output is correct
4 Correct 180 ms 9952 KB Output is correct
5 Correct 177 ms 9900 KB Output is correct
6 Correct 184 ms 10072 KB Output is correct
7 Correct 173 ms 9896 KB Output is correct
8 Correct 171 ms 10008 KB Output is correct
9 Correct 154 ms 9900 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3920 KB Output is correct
2 Correct 24 ms 4580 KB Output is correct
3 Correct 142 ms 8660 KB Output is correct
4 Correct 242 ms 10040 KB Output is correct
5 Correct 214 ms 10008 KB Output is correct
6 Correct 187 ms 10028 KB Output is correct
7 Correct 205 ms 9992 KB Output is correct
8 Correct 204 ms 10016 KB Output is correct
9 Correct 279 ms 10052 KB Output is correct
10 Correct 239 ms 10056 KB Output is correct
11 Correct 251 ms 10228 KB Output is correct
12 Correct 232 ms 10240 KB Output is correct
13 Correct 248 ms 10224 KB Output is correct
14 Correct 259 ms 10300 KB Output is correct
15 Correct 211 ms 9988 KB Output is correct
16 Correct 190 ms 9980 KB Output is correct
17 Correct 259 ms 10240 KB Output is correct
18 Correct 242 ms 10232 KB Output is correct
19 Correct 202 ms 10076 KB Output is correct
20 Correct 181 ms 10236 KB Output is correct
21 Correct 200 ms 10180 KB Output is correct
22 Correct 222 ms 10356 KB Output is correct
23 Correct 220 ms 10568 KB Output is correct
24 Correct 242 ms 10572 KB Output is correct
25 Correct 301 ms 10276 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 4520 KB Output is correct
2 Correct 30 ms 4600 KB Output is correct
3 Correct 251 ms 10244 KB Output is correct
4 Correct 270 ms 10484 KB Output is correct
5 Correct 345 ms 11084 KB Output is correct
6 Correct 308 ms 11160 KB Output is correct
7 Correct 313 ms 10996 KB Output is correct
8 Correct 321 ms 10972 KB Output is correct
9 Correct 255 ms 8696 KB Output is correct
10 Correct 240 ms 8900 KB Output is correct
11 Correct 289 ms 9136 KB Output is correct
12 Correct 276 ms 10340 KB Output is correct
13 Correct 327 ms 10664 KB Output is correct
14 Correct 333 ms 10916 KB Output is correct
15 Correct 293 ms 10880 KB Output is correct
16 Correct 248 ms 9400 KB Output is correct
17 Correct 245 ms 10416 KB Output is correct
18 Correct 235 ms 10468 KB Output is correct
19 Correct 201 ms 10512 KB Output is correct
20 Correct 201 ms 10544 KB Output is correct
21 Correct 267 ms 11372 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 4600 KB Output is correct
2 Correct 33 ms 4520 KB Output is correct
3 Correct 212 ms 10244 KB Output is correct
4 Correct 272 ms 10388 KB Output is correct
5 Correct 278 ms 10516 KB Output is correct
6 Correct 323 ms 10972 KB Output is correct
7 Correct 226 ms 10284 KB Output is correct
8 Correct 229 ms 10344 KB Output is correct
9 Correct 249 ms 10488 KB Output is correct
10 Correct 316 ms 11028 KB Output is correct
11 Correct 301 ms 10992 KB Output is correct
12 Correct 292 ms 10980 KB Output is correct
13 Correct 304 ms 9028 KB Output is correct
14 Correct 276 ms 8856 KB Output is correct
15 Correct 272 ms 9048 KB Output is correct
16 Correct 236 ms 8904 KB Output is correct
17 Correct 304 ms 9108 KB Output is correct
18 Correct 244 ms 8860 KB Output is correct
19 Correct 280 ms 10324 KB Output is correct
20 Correct 296 ms 10532 KB Output is correct
21 Correct 308 ms 10876 KB Output is correct
22 Correct 337 ms 10896 KB Output is correct
23 Correct 336 ms 10876 KB Output is correct
24 Correct 269 ms 10860 KB Output is correct
25 Correct 324 ms 10860 KB Output is correct
26 Correct 290 ms 10868 KB Output is correct
27 Correct 230 ms 10604 KB Output is correct
28 Correct 219 ms 10536 KB Output is correct
29 Correct 237 ms 10732 KB Output is correct
30 Correct 241 ms 10492 KB Output is correct
31 Correct 200 ms 10536 KB Output is correct
32 Correct 233 ms 10452 KB Output is correct
33 Correct 270 ms 10552 KB Output is correct
34 Correct 230 ms 10512 KB Output is correct
35 Correct 200 ms 10436 KB Output is correct
36 Correct 244 ms 10396 KB Output is correct
37 Correct 223 ms 10720 KB Output is correct
38 Correct 231 ms 10472 KB Output is correct
39 Correct 301 ms 11396 KB Output is correct
40 Correct 318 ms 11404 KB Output is correct
41 Correct 375 ms 11420 KB Output is correct
42 Correct 294 ms 11408 KB Output is correct