oj.uz

Submission #1015481

# Submission time Handle Problem Language Result Execution time Memory
1015481 2024-07-06T11:32:54 Z mansur Highway Tolls (IOI18_highway) C++17
18 / 100
 108 ms 145300 KB 
#include "highway.h"
#include<bits/stdc++.h>
 
using namespace std;
 
#define rall(s) s.rbegin(), s.rend()
#define all(s) s.begin(), s.end()
#define sz(s) (int)s.size()
#define s second
#define f first
 
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
 
const int N = 1e6;
 
vector<pii> g[N], s[N], h;
 
void dfs(int u, int id, int dt) {
	if (dt > N) exit(0);
	s[dt].push_back({u, id});
	for (auto [to, i]: g[u]) {
		if (i == id) continue;
		dfs(to, i, dt + 1);
	}
}
 
void dsf(int u, int id, int dt) {
	if (!dt) {
		h.push_back({id, u});
		return;
	}
	for (auto [to, i]: g[u]) {
 		if (i == id) continue;
		dsf(to, i, dt - 1);
	}
}
 
void find_pair(int n, vector<int> u, vector<int> v, int a, int b) {
	if (sz(u) == 4 && n == 4) {
		answer(1, 3);
		return;
	}
	for (int i = 0; i < sz(u); i++) {
		g[u[i]].push_back({v[i], i});
		g[v[i]].push_back({u[i], i});
	}
	vector<int> w(sz(u));
	ll dt = ask(w);	
	int l = 0, r = sz(u) - 1;
	while (l <= r) {
		int m = (l + r) / 2;
		for (int i = 0; i <= m; i++) w[i] = 1;
		if (ask(w) == dt) l = m + 1;
		else r = m - 1;
		for (int i = 0; i <= m; i++) w[i] = 0;
	}
	int x = u[l], y = v[l];
	dfs(y, l, 0);
	l = 0, r = n;
	while (l <= r) {
		int m = (l + r) / 2;
		for (int i = m; i <= n; i++) {
			for (auto [vt, id]: s[i]) {
				w[id] = 1;
			}
		}
		if (ask(w) == dt) r = m - 1;
		else l = m + 1;
		for (int i = m; i <= n; i++) {
			for (auto [vt, id]: s[i]) {
				w[id] = 0;
			}
		}
	}
	int z = r;
	l = 0, r = sz(s[z]) - 1;
	while (l <= r) {
		int m = (l + r) / 2;
		for (int i = 0; i <= m; i++) {
			w[s[z][i].s] = 1;
		}
		if (ask(w) == dt) l = m + 1;
		else r = m - 1;
		for (int i = 0; i <= m; i++) {
			w[s[z][i].s] = 0;
		}
	}
	x = s[z][l].f;
	dt /= a;
	dsf(x, -1, dt);
	l = 0, r = sz(h) - 1;
	while (l <= r) {
		int m = (l + r) / 2;
		for (int i = 0; i <= m; i++) w[h[i].f] = 1;
		if (ask(w) == dt * 1ll * a) l = m + 1;
		else r = m - 1;
		for (int i = 0; i <= m; i++) w[h[i].f] = 0; 
	}
	answer(x, h[l].s);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 47448 KB Output is correct
2 Correct 15 ms 47876 KB Output is correct
3 Correct 91 ms 52764 KB Output is correct
4 Correct 97 ms 53884 KB Output is correct
5 Correct 85 ms 53728 KB Output is correct
6 Correct 89 ms 53512 KB Output is correct
7 Correct 98 ms 53620 KB Output is correct
8 Correct 90 ms 53560 KB Output is correct
9 Correct 81 ms 52560 KB Output is correct
10 Correct 96 ms 53576 KB Output is correct
11 Correct 85 ms 53400 KB Output is correct
12 Correct 108 ms 53024 KB Output is correct
13 Correct 94 ms 54596 KB Output is correct
14 Correct 95 ms 52912 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 48472 KB Output is correct
2 Correct 23 ms 49856 KB Output is correct
3 Correct 33 ms 49176 KB Output is correct
4 Correct 76 ms 57184 KB Output is correct
5 Correct 73 ms 57272 KB Output is correct
6 Correct 77 ms 58736 KB Output is correct
7 Correct 73 ms 52228 KB Output is correct
8 Correct 74 ms 57928 KB Output is correct
9 Correct 90 ms 54112 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 47448 KB Output is correct
2 Correct 17 ms 48056 KB Output is correct
3 Correct 65 ms 52040 KB Output is correct
4 Correct 87 ms 53468 KB Output is correct
5 Correct 79 ms 52304 KB Output is correct
6 Correct 85 ms 53456 KB Output is correct
7 Correct 84 ms 52300 KB Output is correct
8 Correct 93 ms 52524 KB Output is correct
9 Correct 98 ms 52784 KB Output is correct
10 Correct 89 ms 52892 KB Output is correct
11 Correct 91 ms 52664 KB Output is correct
12 Correct 95 ms 55068 KB Output is correct
13 Correct 88 ms 53104 KB Output is correct
14 Correct 102 ms 53172 KB Output is correct
15 Correct 85 ms 53624 KB Output is correct
16 Correct 93 ms 53672 KB Output is correct
17 Correct 91 ms 52928 KB Output is correct
18 Correct 89 ms 52832 KB Output is correct
19 Correct 87 ms 52520 KB Output is correct
20 Correct 92 ms 55456 KB Output is correct
21 Incorrect 86 ms 54776 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 104 ms 145300 KB Output is incorrect: answered not exactly once.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 99 ms 144976 KB Output is incorrect: answered not exactly once.
2 Halted 0 ms 0 KB -