oj.uz

Submission #794163

# Submission time Handle Problem Language Result Execution time Memory
794163 2023-07-26T10:08:25 Z Sohsoh84 Highway Tolls (IOI18_highway) C++17
51 / 100
 153 ms 41644 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];
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 find(int root) {
	par[root] = -1;
	dfs_order.clear();

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

	while (l < r) {
		int mid = (l + r) >> 1;	
		if (get(1, mid) == mx) 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);
	int 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 13 ms 27728 KB Output is correct
2 Correct 13 ms 27728 KB Output is correct
3 Correct 14 ms 27676 KB Output is correct
4 Correct 14 ms 27728 KB Output is correct
5 Correct 14 ms 27728 KB Output is correct
6 Correct 14 ms 27728 KB Output is correct
7 Correct 14 ms 27728 KB Output is correct
8 Correct 14 ms 27664 KB Output is correct
9 Correct 13 ms 27680 KB Output is correct
10 Correct 14 ms 27676 KB Output is correct
11 Correct 14 ms 27728 KB Output is correct
12 Correct 14 ms 27688 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 27728 KB Output is correct
2 Correct 21 ms 28456 KB Output is correct
3 Correct 112 ms 34728 KB Output is correct
4 Correct 125 ms 34736 KB Output is correct
5 Correct 113 ms 34732 KB Output is correct
6 Correct 117 ms 34732 KB Output is correct
7 Correct 139 ms 34832 KB Output is correct
8 Correct 121 ms 34720 KB Output is correct
9 Correct 116 ms 34724 KB Output is correct
10 Correct 129 ms 34760 KB Output is correct
11 Correct 130 ms 36296 KB Output is correct
12 Correct 116 ms 37292 KB Output is correct
13 Correct 148 ms 36564 KB Output is correct
14 Correct 118 ms 36600 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 29244 KB Output is correct
2 Correct 32 ms 30892 KB Output is correct
3 Correct 45 ms 32472 KB Output is correct
4 Correct 85 ms 41636 KB Output is correct
5 Correct 138 ms 41636 KB Output is correct
6 Correct 105 ms 41644 KB Output is correct
7 Correct 110 ms 41644 KB Output is correct
8 Correct 107 ms 41644 KB Output is correct
9 Correct 111 ms 41640 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 27748 KB Output is correct
2 Correct 26 ms 28504 KB Output is correct
3 Correct 96 ms 33316 KB Output is correct
4 Correct 125 ms 34736 KB Output is correct
5 Correct 94 ms 34724 KB Output is correct
6 Correct 99 ms 34736 KB Output is correct
7 Correct 128 ms 34728 KB Output is correct
8 Correct 116 ms 34716 KB Output is correct
9 Correct 133 ms 34800 KB Output is correct
10 Correct 134 ms 34724 KB Output is correct
11 Correct 133 ms 35844 KB Output is correct
12 Correct 135 ms 37272 KB Output is correct
13 Correct 139 ms 36672 KB Output is correct
14 Correct 108 ms 37096 KB Output is correct
15 Correct 131 ms 34732 KB Output is correct
16 Correct 137 ms 34732 KB Output is correct
17 Correct 142 ms 36748 KB Output is correct
18 Correct 124 ms 36876 KB Output is correct
19 Correct 134 ms 34724 KB Output is correct
20 Correct 153 ms 37688 KB Output is correct
21 Correct 133 ms 34960 KB Output is correct
22 Correct 123 ms 34956 KB Output is correct
23 Correct 102 ms 35080 KB Output is correct
24 Correct 130 ms 35736 KB Output is correct
25 Correct 127 ms 40944 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 28596 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 28592 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -