oj.uz

Submission #1015468

# Submission time Handle Problem Language Result Execution time Memory
1015468 2024-07-06T11:19:43 Z mansur Highway Tolls (IOI18_highway) C++17
18 / 100
 239 ms 262144 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) {
	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 47192 KB Output is correct
3 Correct 12 ms 47192 KB Output is correct
4 Correct 9 ms 47192 KB Output is correct
5 Correct 8 ms 47192 KB Output is correct
6 Correct 9 ms 47392 KB Output is correct
7 Correct 8 ms 47192 KB Output is correct
8 Correct 8 ms 47192 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 8 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 16 ms 47832 KB Output is correct
3 Correct 83 ms 52736 KB Output is correct
4 Correct 98 ms 53668 KB Output is correct
5 Correct 85 ms 53612 KB Output is correct
6 Correct 95 ms 53516 KB Output is correct
7 Correct 90 ms 53776 KB Output is correct
8 Correct 90 ms 53652 KB Output is correct
9 Correct 76 ms 52524 KB Output is correct
10 Correct 92 ms 53580 KB Output is correct
11 Correct 99 ms 53392 KB Output is correct
12 Correct 91 ms 53016 KB Output is correct
13 Correct 89 ms 54668 KB Output is correct
14 Correct 74 ms 52904 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 48472 KB Output is correct
2 Correct 25 ms 49752 KB Output is correct
3 Correct 26 ms 49176 KB Output is correct
4 Correct 78 ms 57180 KB Output is correct
5 Correct 70 ms 57280 KB Output is correct
6 Correct 70 ms 59104 KB Output is correct
7 Correct 73 ms 52240 KB Output is correct
8 Correct 67 ms 57844 KB Output is correct
9 Correct 80 ms 54008 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 47448 KB Output is correct
2 Correct 18 ms 47864 KB Output is correct
3 Correct 60 ms 52164 KB Output is correct
4 Correct 73 ms 53452 KB Output is correct
5 Correct 71 ms 52452 KB Output is correct
6 Correct 76 ms 53560 KB Output is correct
7 Correct 73 ms 52528 KB Output is correct
8 Correct 65 ms 52444 KB Output is correct
9 Correct 83 ms 52796 KB Output is correct
10 Correct 82 ms 52776 KB Output is correct
11 Correct 73 ms 52516 KB Output is correct
12 Correct 88 ms 55060 KB Output is correct
13 Correct 77 ms 52984 KB Output is correct
14 Correct 83 ms 53392 KB Output is correct
15 Correct 84 ms 53632 KB Output is correct
16 Correct 68 ms 53680 KB Output is correct
17 Correct 77 ms 52724 KB Output is correct
18 Correct 68 ms 52660 KB Output is correct
19 Correct 66 ms 52444 KB Output is correct
20 Correct 93 ms 55452 KB Output is correct
21 Incorrect 77 ms 55020 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 229 ms 262144 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 239 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -