oj.uz

Submission #75232

# Submission time Handle Problem Language Result Execution time Memory
75232 2018-09-08T17:48:28 Z ainta Highway Tolls (IOI18_highway) C++17
5 / 100
 326 ms 9884 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]);
	}
	int 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]) {
				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 4 ms 2684 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 2692 KB Output is correct
6 Correct 4 ms 2680 KB Output is correct
7 Correct 3 ms 2724 KB Output is correct
8 Correct 4 ms 2684 KB Output is correct
9 Correct 4 ms 2688 KB Output is correct
10 Correct 3 ms 2768 KB Output is correct
11 Correct 5 ms 2692 KB Output is correct
12 Correct 5 ms 2680 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2740 KB Output is correct
2 Correct 29 ms 3448 KB Output is correct
3 Correct 204 ms 8864 KB Output is correct
4 Correct 250 ms 8964 KB Output is correct
5 Correct 181 ms 8868 KB Output is correct
6 Correct 244 ms 8876 KB Output is correct
7 Correct 214 ms 8856 KB Output is correct
8 Correct 196 ms 8840 KB Output is correct
9 Correct 207 ms 8864 KB Output is correct
10 Correct 261 ms 8964 KB Output is correct
11 Correct 218 ms 9064 KB Output is correct
12 Correct 215 ms 9096 KB Output is correct
13 Correct 224 ms 9052 KB Output is correct
14 Incorrect 279 ms 9064 KB Output is incorrect: {s, t} is wrong.

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3448 KB Output is correct
2 Correct 43 ms 4024 KB Output is correct
3 Correct 49 ms 4700 KB Output is correct
4 Correct 177 ms 8776 KB Output is correct
5 Correct 175 ms 8700 KB Output is correct
6 Correct 169 ms 8924 KB Output is correct
7 Correct 204 ms 8760 KB Output is correct
8 Correct 177 ms 8832 KB Output is correct
9 Incorrect 162 ms 9084 KB Output is incorrect: {s, t} is wrong.

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2728 KB Output is correct
2 Correct 38 ms 3368 KB Output is correct
3 Correct 159 ms 7480 KB Output is correct
4 Correct 210 ms 8864 KB Output is correct
5 Correct 209 ms 8808 KB Output is correct
6 Correct 230 ms 8876 KB Output is correct
7 Correct 202 ms 8808 KB Output is correct
8 Correct 189 ms 8808 KB Output is correct
9 Incorrect 310 ms 9036 KB Output is incorrect: {s, t} is wrong.
10 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3392 KB Output is correct
2 Correct 29 ms 3448 KB Output is correct
3 Correct 243 ms 9068 KB Output is correct
4 Correct 280 ms 9280 KB Output is correct
5 Incorrect 323 ms 9884 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 21 ms 3396 KB Output is correct
2 Correct 25 ms 3424 KB Output is correct
3 Correct 245 ms 9064 KB Output is correct
4 Correct 273 ms 9184 KB Output is correct
5 Correct 268 ms 9356 KB Output is correct
6 Correct 326 ms 9792 KB Output is correct
7 Correct 228 ms 9080 KB Output is correct
8 Correct 233 ms 9172 KB Output is correct
9 Incorrect 226 ms 9384 KB Output is incorrect: {s, t} is wrong.
10 Halted 0 ms 0 KB -