oj.uz

Submission #794183

# Submission time Handle Problem Language Result Execution time Memory
794183 2023-07-26T10:20:48 Z Sohsoh84 Highway Tolls (IOI18_highway) C++17
51 / 100
 161 ms 41728 KB 
#include "highway.h"
#include <bits/stdc++.h>

using namespace std;

#define sep		' '
#define debug(x)	cerr << #x << ": " << x << endl;
#define all(x)		(x).begin(), (x).end()

const int MAXN = 1e6 + 10;

int askcnt = 0;
int from[MAXN], to[MAXN], n, m, par[MAXN], mn;
vector<int> adj[MAXN], dfs_order, fuck;

inline int f(int ind, int v) {
	return from[ind] ^ to[ind] ^ v;
}

void dfs(int v, int p) {
	dfs_order.push_back(v);
	for (int ind : adj[v]) {
		int u = f(ind, v);
		if (u == p) continue;

		par[u] = ind;
		dfs(u, v);
	}
}


inline vector<int> seg(int l, int r) {
	vector<int> ans;
	for (int i = l; i <= r; i++)
		ans.push_back(par[dfs_order[i]]);

	return ans;
}

inline int get(vector<int> vec) {
	vector<int> W(m);
	for (int i = 0; i < m; i++) W[i] = 1;
	for (int e : fuck)
		W[e] = 0;

	for (int e : vec)
		W[e] = 1;

	return ask(W);
}

inline int getp(vector<int> vec) {
	vector<int> W(m);
	for (int i = 0; i < m; i++) 
		W[i] = 1;
	for (int e : vec)
		W[e] = 0;

	return ask(W);
}

inline int get(int l, int r) {
	return get(seg(l, r));
}

inline int getp(int l, int r) {
	return getp(seg(l, r));
}

inline int find(int root) {
	par[root] = -1;
	dfs_order.clear();

	dfs(root, root);
	int l = 1, r = int(dfs_order.size()) - 1;

	while (l < r) {
		int mid = (l + r) >> 1;	
		if (getp(1, mid) == mn) r = mid;
		else l = mid + 1;
	}

	return dfs_order[l];

}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int dist[MAXN];

inline vector<int> random_spt() {
	for (int v = 0; v < n; v++)
		shuffle(all(adj[v]), rng);

	vector<int> ans;
	queue<int> q;
	int v = 0;

	memset(dist, 63, sizeof dist);
	q.push(v);
	dist[v] = 0;

	while (!q.empty()) {
		int v = q.front();
		q.pop();

		for (int ind : adj[v]) {
			int u = f(ind, v);
			if (dist[u] > dist[v] + 1) {
				dist[u] = dist[v] + 1;
				q.push(u);
				ans.push_back(ind);
			}
		}
	}

	return ans;
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	m = U.size();
	n = N;

	for (int i = 0; i < m; i++) {
		from[i] = U[i];
		to[i] = V[i];

		adj[from[i]].push_back(i);
		adj[to[i]].push_back(i);
	}

	for (int i = 0; i < m; i++)
		fuck.push_back(i);

	mn = get({});
	while (true) {
		vector<int> tmp = random_spt();

		if (getp(tmp) == mn) {
			fuck = tmp;
			for (int i = 0; i < n; i++) adj[i].clear();
			for (int ind : tmp) {
				adj[from[ind]].push_back(ind);
				adj[to[ind]].push_back(ind);
			}

			break;
		}
	}

	int v = find(0);
	int u = find(v);

	answer(u, v);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 27728 KB Output is correct
2 Correct 14 ms 27680 KB Output is correct
3 Correct 15 ms 27732 KB Output is correct
4 Correct 15 ms 27676 KB Output is correct
5 Correct 15 ms 27728 KB Output is correct
6 Correct 15 ms 27728 KB Output is correct
7 Correct 14 ms 27728 KB Output is correct
8 Correct 14 ms 27728 KB Output is correct
9 Correct 17 ms 27748 KB Output is correct
10 Correct 14 ms 27728 KB Output is correct
11 Correct 14 ms 27720 KB Output is correct
12 Correct 14 ms 27728 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 27756 KB Output is correct
2 Correct 26 ms 28488 KB Output is correct
3 Correct 94 ms 34716 KB Output is correct
4 Correct 102 ms 34724 KB Output is correct
5 Correct 106 ms 34724 KB Output is correct
6 Correct 131 ms 34788 KB Output is correct
7 Correct 132 ms 34720 KB Output is correct
8 Correct 105 ms 34788 KB Output is correct
9 Correct 101 ms 34732 KB Output is correct
10 Correct 120 ms 34724 KB Output is correct
11 Correct 131 ms 36364 KB Output is correct
12 Correct 146 ms 37284 KB Output is correct
13 Correct 149 ms 36468 KB Output is correct
14 Correct 123 ms 36596 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 29268 KB Output is correct
2 Correct 33 ms 30884 KB Output is correct
3 Correct 43 ms 32476 KB Output is correct
4 Correct 107 ms 41640 KB Output is correct
5 Correct 117 ms 41632 KB Output is correct
6 Correct 135 ms 41672 KB Output is correct
7 Correct 89 ms 41640 KB Output is correct
8 Correct 118 ms 41644 KB Output is correct
9 Correct 87 ms 41728 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 27728 KB Output is correct
2 Correct 26 ms 28532 KB Output is correct
3 Correct 101 ms 33292 KB Output is correct
4 Correct 140 ms 34716 KB Output is correct
5 Correct 124 ms 34720 KB Output is correct
6 Correct 134 ms 34736 KB Output is correct
7 Correct 132 ms 34716 KB Output is correct
8 Correct 161 ms 34708 KB Output is correct
9 Correct 129 ms 34724 KB Output is correct
10 Correct 150 ms 34724 KB Output is correct
11 Correct 126 ms 35840 KB Output is correct
12 Correct 117 ms 37268 KB Output is correct
13 Correct 153 ms 36620 KB Output is correct
14 Correct 146 ms 37088 KB Output is correct
15 Correct 126 ms 34708 KB Output is correct
16 Correct 101 ms 34860 KB Output is correct
17 Correct 145 ms 36744 KB Output is correct
18 Correct 151 ms 36920 KB Output is correct
19 Correct 114 ms 34728 KB Output is correct
20 Correct 139 ms 37672 KB Output is correct
21 Correct 131 ms 35052 KB Output is correct
22 Correct 121 ms 34960 KB Output is correct
23 Correct 134 ms 35084 KB Output is correct
24 Correct 115 ms 35748 KB Output is correct
25 Correct 140 ms 40920 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 95 ms 28548 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 96 ms 28556 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -