oj.uz

Submission #415694

# Submission time Handle Problem Language Result Execution time Memory
415694 2021-06-01T11:35:40 Z SuhaibSawalha1 Highway Tolls (IOI18_highway) C++17
51 / 100
 326 ms 262148 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;

vector<vector<array<int, 2>>> adj;
vector<array<int, 2>> to_ask;
vector<int> ak;
int n, m, A, B, dp;
long long W;

void dfs (int u, int p, int d = 1) {
	for (auto &v : adj[u]) {
		if (v[0] ^ p) {
			if (d == dp) {
				to_ask.push_back(v);
			}	
			else {
				dfs(v[0], u, d + 1);
			}
		}
	}
}

void dfs2 (int u, int p) {
	for (auto &v : adj[u]) {
		if (v[0] ^ p) {
			ak[v[1]] = 1;
			dfs2(v[0], u);
		}
	}
}

int first () {
	int l = 0, r = m - 1;
	W = ask(vector<int>(m, 0));
	while (l < r) {
		int mid = (l + r) / 2;
		vector<int> ak(m, 0);
		fill(ak.begin(), ak.begin() + mid + 1, 1);
		if (ask(ak) != W) {
			r = mid;
		}
		else {
			l = mid + 1;
		}
	}
	return l;
}



void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	n = N;
	m = U.size();
	::A = A;
	::B = B;
	adj.assign(n, {});
	for (int i = 0; i < m; ++i) {
		adj[U[i]].push_back({V[i], i});
		adj[V[i]].push_back({U[i], i});
	}	
	int f = first();
	int u = U[f], v = V[f];
	ak.assign(m, 0);
	dfs2(u, v);
	long long WE = ask(ak);
	int s = W / A;
	auto go = [&] (int u, int v, int dp) {
		if (!dp) {
			return u;
		}
		::dp = dp;
		to_ask.clear();
		dfs(u, v);
		int l = 0, r = to_ask.size() - 1;
		while (l < r) {
			int mid = (l + r) / 2;
			vector<int> ak(m, 0);
			for (int i = 0; i <= mid; ++i) {
				ak[to_ask[i][1]] = 1;
			}
			if (ask(ak) != s * 1LL * A) {
				r = mid;
			}
			else {
				l = mid + 1;
			}
		}
		return to_ask[l][0];
	};
	for (int i = 0; i <= s; ++i) {
		if (i * 1LL * A + (s - i) * 1LL * B == WE) {
			return answer(go(u, v, s - i), go(v, u, i - 1));
		}
	}
	assert(0);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 328 KB Output is correct
2 Correct 18 ms 1144 KB Output is correct
3 Correct 248 ms 8256 KB Output is correct
4 Correct 204 ms 8196 KB Output is correct
5 Correct 228 ms 8092 KB Output is correct
6 Correct 213 ms 7948 KB Output is correct
7 Correct 162 ms 8104 KB Output is correct
8 Correct 188 ms 7832 KB Output is correct
9 Correct 116 ms 7892 KB Output is correct
10 Correct 203 ms 8104 KB Output is correct
11 Correct 98 ms 8148 KB Output is correct
12 Correct 133 ms 8620 KB Output is correct
13 Correct 106 ms 7740 KB Output is correct
14 Correct 119 ms 8384 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1096 KB Output is correct
2 Correct 24 ms 1956 KB Output is correct
3 Correct 55 ms 3644 KB Output is correct
4 Correct 96 ms 8500 KB Output is correct
5 Correct 141 ms 8560 KB Output is correct
6 Correct 191 ms 10480 KB Output is correct
7 Correct 143 ms 10952 KB Output is correct
8 Correct 210 ms 9000 KB Output is correct
9 Correct 172 ms 10108 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 328 KB Output is correct
2 Correct 12 ms 1124 KB Output is correct
3 Correct 103 ms 6172 KB Output is correct
4 Correct 145 ms 8036 KB Output is correct
5 Correct 177 ms 7948 KB Output is correct
6 Correct 114 ms 7812 KB Output is correct
7 Correct 219 ms 7828 KB Output is correct
8 Correct 139 ms 7776 KB Output is correct
9 Correct 221 ms 8260 KB Output is correct
10 Correct 137 ms 8144 KB Output is correct
11 Correct 204 ms 8208 KB Output is correct
12 Correct 127 ms 8380 KB Output is correct
13 Correct 125 ms 8504 KB Output is correct
14 Correct 162 ms 8368 KB Output is correct
15 Correct 102 ms 7828 KB Output is correct
16 Correct 191 ms 7712 KB Output is correct
17 Correct 156 ms 8240 KB Output is correct
18 Correct 196 ms 8496 KB Output is correct
19 Correct 208 ms 7836 KB Output is correct
20 Correct 117 ms 7740 KB Output is correct
21 Correct 107 ms 9228 KB Output is correct
22 Correct 183 ms 9204 KB Output is correct
23 Correct 184 ms 8676 KB Output is correct
24 Correct 235 ms 8840 KB Output is correct
25 Correct 167 ms 12384 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 326 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 235 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -