oj.uz

Submission #817827

# Submission time Handle Problem Language Result Execution time Memory
817827 2023-08-09T17:23:43 Z pavement Highway Tolls (IOI18_highway) C++17
51 / 100
 137 ms 35580 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define eb emplace_back
#define mt make_tuple

using ll = long long;
using ii = pair<int, int>;

int ed;
vector<int> ndep;
vector<vector<int> > U_edges, V_edges;
vector<vector<ii> > adj;

void dfs(int u, vector<vector<int> > &edges, int dep = 0, int e = -1) {
	ndep[u] = dep;
	for (auto [v, idx] : adj[u]) if (v != e && idx != ed) {
		edges[dep].pb(idx);
		dfs(v, edges, dep + 1, u);
	}
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
	ndep.resize(N);
	adj.resize(N);
	int M = (int)U.size();
	vector<int> cur;
	for (int i = 0; i < M; i++) {
		adj[U[i]].eb(V[i], i);
		adj[V[i]].eb(U[i], i);
		cur.pb(i);
	}
	ll original = ask(vector<int>(M, 0));
	while ((int)cur.size() > 1) {
		vector<int> w(M, 0);
		for (int i = 0; i < (int)cur.size() / 2; i++) {
			w[cur[i]] = 1;
		}
		if (ask(w) > original) {
			int new_sz = (int)cur.size() / 2;
			while ((int)cur.size() != new_sz) cur.pop_back();
		} else {
			int new_sz = ((int)cur.size() + 1) / 2;
			reverse(cur.begin(), cur.end());
			while ((int)cur.size() != new_sz) cur.pop_back();
			reverse(cur.begin(), cur.end());
		}
	}
	ed = cur[0];
	U_edges.resize(N);
	V_edges.resize(N);
	dfs(U[ed], U_edges);
	dfs(V[ed], V_edges);
	vector<int> w(M, 0);
	for (auto edges_by_dep : U_edges) {
		for (auto edge : edges_by_dep) {
			w[edge] = 1;
		}
	}
	ll tmp = ask(w);
	int U_len = (tmp - original) / (B - A);
	int V_len = original / A - U_len - 1;
	int S, T;
	for (auto [len, edges, R, W] : {mt(U_len, U_edges, &S, U), mt(V_len, V_edges, &T, V)}) {
		if (len) {
			vector<int> cur = edges[len - 1];
			while ((int)cur.size() > 1) {
				vector<int> w(M, 0);
				for (int i = 0; i < (int)cur.size() / 2; i++) {
					w[cur[i]] = 1;
				}
				if (ask(w) > original) {
					int new_sz = (int)cur.size() / 2;
					while ((int)cur.size() != new_sz) cur.pop_back();
				} else {
					int new_sz = ((int)cur.size() + 1) / 2;
					reverse(cur.begin(), cur.end());
					while ((int)cur.size() != new_sz) cur.pop_back();
					reverse(cur.begin(), cur.end());
				}
			}
			*R = (ndep[U[cur[0]]] > ndep[V[cur[0]]] ? U[cur[0]] : V[cur[0]]);
		} else {
			*R = W[ed];
		}
	}
	answer(S, T);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 9 ms 2680 KB Output is correct
3 Correct 137 ms 21508 KB Output is correct
4 Correct 103 ms 21456 KB Output is correct
5 Correct 95 ms 21416 KB Output is correct
6 Correct 85 ms 21368 KB Output is correct
7 Correct 108 ms 21360 KB Output is correct
8 Correct 114 ms 21364 KB Output is correct
9 Correct 112 ms 21328 KB Output is correct
10 Correct 88 ms 21372 KB Output is correct
11 Correct 98 ms 23880 KB Output is correct
12 Correct 83 ms 25732 KB Output is correct
13 Correct 97 ms 24216 KB Output is correct
14 Correct 93 ms 24580 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4024 KB Output is correct
2 Correct 16 ms 7784 KB Output is correct
3 Correct 33 ms 11788 KB Output is correct
4 Correct 66 ms 32008 KB Output is correct
5 Correct 89 ms 32044 KB Output is correct
6 Correct 71 ms 33856 KB Output is correct
7 Correct 129 ms 35580 KB Output is correct
8 Correct 91 ms 32868 KB Output is correct
9 Correct 118 ms 33236 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 9 ms 2608 KB Output is correct
3 Correct 94 ms 16764 KB Output is correct
4 Correct 76 ms 21412 KB Output is correct
5 Correct 126 ms 21284 KB Output is correct
6 Correct 74 ms 21416 KB Output is correct
7 Correct 106 ms 21044 KB Output is correct
8 Correct 102 ms 21300 KB Output is correct
9 Correct 87 ms 21332 KB Output is correct
10 Correct 116 ms 21428 KB Output is correct
11 Correct 100 ms 23568 KB Output is correct
12 Correct 85 ms 25668 KB Output is correct
13 Correct 79 ms 25024 KB Output is correct
14 Correct 112 ms 24460 KB Output is correct
15 Correct 85 ms 21296 KB Output is correct
16 Correct 69 ms 20984 KB Output is correct
17 Correct 90 ms 23936 KB Output is correct
18 Correct 88 ms 24916 KB Output is correct
19 Correct 95 ms 21392 KB Output is correct
20 Correct 101 ms 26468 KB Output is correct
21 Correct 94 ms 22400 KB Output is correct
22 Correct 99 ms 22336 KB Output is correct
23 Correct 77 ms 21680 KB Output is correct
24 Correct 107 ms 22652 KB Output is correct
25 Correct 96 ms 34520 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 16 ms 5844 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 16 ms 5828 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -