oj.uz

Submission #75234

# Submission time Handle Problem Language Result Execution time Memory
75234 2018-09-08T17:55:43 Z ainta Highway Tolls (IOI18_highway) C++17
51 / 100
 317 ms 9748 KB 
#include "highway.h"
#include <cstdio>
#include <algorithm>
#define N_ 101000
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;
		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] && y <= root) {
				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;
		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 4 ms 2680 KB Output is correct
2 Correct 5 ms 2680 KB Output is correct
3 Correct 4 ms 2600 KB Output is correct
4 Correct 4 ms 2684 KB Output is correct
5 Correct 4 ms 2680 KB Output is correct
6 Correct 4 ms 2596 KB Output is correct
7 Correct 4 ms 2600 KB Output is correct
8 Correct 4 ms 2696 KB Output is correct
9 Correct 4 ms 2688 KB Output is correct
10 Correct 4 ms 2632 KB Output is correct
11 Correct 4 ms 2812 KB Output is correct
12 Correct 4 ms 2680 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2760 KB Output is correct
2 Correct 27 ms 3372 KB Output is correct
3 Correct 244 ms 8852 KB Output is correct
4 Correct 268 ms 8900 KB Output is correct
5 Correct 227 ms 8448 KB Output is correct
6 Correct 233 ms 8840 KB Output is correct
7 Correct 208 ms 8384 KB Output is correct
8 Correct 242 ms 8868 KB Output is correct
9 Correct 208 ms 8596 KB Output is correct
10 Correct 214 ms 8488 KB Output is correct
11 Correct 223 ms 9048 KB Output is correct
12 Correct 229 ms 8860 KB Output is correct
13 Correct 221 ms 8784 KB Output is correct
14 Correct 229 ms 8920 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3140 KB Output is correct
2 Correct 19 ms 3832 KB Output is correct
3 Correct 58 ms 4636 KB Output is correct
4 Correct 150 ms 8168 KB Output is correct
5 Correct 164 ms 7824 KB Output is correct
6 Correct 201 ms 8700 KB Output is correct
7 Correct 174 ms 8644 KB Output is correct
8 Correct 190 ms 8460 KB Output is correct
9 Correct 159 ms 8396 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2808 KB Output is correct
2 Correct 24 ms 3360 KB Output is correct
3 Correct 147 ms 7424 KB Output is correct
4 Correct 190 ms 8548 KB Output is correct
5 Correct 195 ms 8408 KB Output is correct
6 Correct 215 ms 8760 KB Output is correct
7 Correct 201 ms 8496 KB Output is correct
8 Correct 189 ms 8492 KB Output is correct
9 Correct 246 ms 8840 KB Output is correct
10 Correct 217 ms 8716 KB Output is correct
11 Correct 243 ms 9144 KB Output is correct
12 Correct 273 ms 9056 KB Output is correct
13 Correct 219 ms 8948 KB Output is correct
14 Correct 214 ms 8864 KB Output is correct
15 Correct 184 ms 8456 KB Output is correct
16 Correct 207 ms 8528 KB Output is correct
17 Correct 250 ms 9032 KB Output is correct
18 Correct 200 ms 8776 KB Output is correct
19 Correct 191 ms 8256 KB Output is correct
20 Correct 208 ms 8804 KB Output is correct
21 Correct 198 ms 8916 KB Output is correct
22 Correct 208 ms 8896 KB Output is correct
23 Correct 242 ms 9412 KB Output is correct
24 Correct 268 ms 9464 KB Output is correct
25 Correct 223 ms 9208 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 3392 KB Output is correct
2 Correct 24 ms 3408 KB Output is correct
3 Correct 250 ms 8932 KB Output is correct
4 Correct 254 ms 9136 KB Output is correct
5 Incorrect 317 ms 9652 KB Output is incorrect: {s, t} is wrong.
6 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 3356 KB Output is correct
2 Correct 27 ms 3388 KB Output is correct
3 Correct 236 ms 8540 KB Output is correct
4 Correct 258 ms 9132 KB Output is correct
5 Correct 271 ms 9164 KB Output is correct
6 Correct 313 ms 9748 KB Output is correct
7 Correct 232 ms 8900 KB Output is correct
8 Correct 249 ms 9116 KB Output is correct
9 Correct 265 ms 9192 KB Output is correct
10 Correct 292 ms 9464 KB Output is correct
11 Incorrect 280 ms 9716 KB Output is incorrect: {s, t} is wrong.
12 Halted 0 ms 0 KB -