oj.uz

Submission #794175

# Submission time Handle Problem Language Result Execution time Memory
794175 2023-07-26T10:17:18 Z Sohsoh84 Highway Tolls (IOI18_highway) C++17
51 / 100
 178 ms 41652 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 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 = rng() % n;

	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 27632 KB Output is correct
3 Correct 16 ms 27676 KB Output is correct
4 Correct 15 ms 27676 KB Output is correct
5 Correct 14 ms 27664 KB Output is correct
6 Correct 17 ms 27676 KB Output is correct
7 Correct 15 ms 27728 KB Output is correct
8 Correct 15 ms 27672 KB Output is correct
9 Correct 14 ms 27680 KB Output is correct
10 Correct 16 ms 27692 KB Output is correct
11 Correct 16 ms 27728 KB Output is correct
12 Correct 17 ms 27632 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 27732 KB Output is correct
2 Correct 23 ms 28528 KB Output is correct
3 Correct 132 ms 34716 KB Output is correct
4 Correct 155 ms 34724 KB Output is correct
5 Correct 136 ms 34712 KB Output is correct
6 Correct 134 ms 34716 KB Output is correct
7 Correct 140 ms 34732 KB Output is correct
8 Correct 154 ms 34728 KB Output is correct
9 Correct 131 ms 34716 KB Output is correct
10 Correct 119 ms 34748 KB Output is correct
11 Correct 178 ms 36300 KB Output is correct
12 Correct 147 ms 37280 KB Output is correct
13 Correct 158 ms 36472 KB Output is correct
14 Correct 150 ms 36584 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 29248 KB Output is correct
2 Correct 31 ms 30852 KB Output is correct
3 Correct 47 ms 32476 KB Output is correct
4 Correct 117 ms 41632 KB Output is correct
5 Correct 87 ms 41636 KB Output is correct
6 Correct 114 ms 41624 KB Output is correct
7 Correct 118 ms 41652 KB Output is correct
8 Correct 117 ms 41636 KB Output is correct
9 Correct 88 ms 41644 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 27728 KB Output is correct
2 Correct 24 ms 28452 KB Output is correct
3 Correct 97 ms 33288 KB Output is correct
4 Correct 162 ms 34708 KB Output is correct
5 Correct 123 ms 34724 KB Output is correct
6 Correct 137 ms 34716 KB Output is correct
7 Correct 106 ms 34728 KB Output is correct
8 Correct 128 ms 34720 KB Output is correct
9 Correct 108 ms 34724 KB Output is correct
10 Correct 155 ms 34728 KB Output is correct
11 Correct 144 ms 35840 KB Output is correct
12 Correct 160 ms 37260 KB Output is correct
13 Correct 153 ms 36632 KB Output is correct
14 Correct 117 ms 37096 KB Output is correct
15 Correct 124 ms 34712 KB Output is correct
16 Correct 129 ms 34720 KB Output is correct
17 Correct 163 ms 36740 KB Output is correct
18 Correct 143 ms 36876 KB Output is correct
19 Correct 127 ms 34708 KB Output is correct
20 Correct 151 ms 37680 KB Output is correct
21 Correct 115 ms 34980 KB Output is correct
22 Correct 134 ms 34952 KB Output is correct
23 Correct 147 ms 35072 KB Output is correct
24 Correct 129 ms 35740 KB Output is correct
25 Correct 158 ms 40920 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 56 ms 28584 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 28584 KB Output isn't correct
2 Halted 0 ms 0 KB -