oj.uz

Submission #794181

# Submission time Handle Problem Language Result Execution time Memory
794181 2023-07-26T10:19:08 Z Sohsoh84 Highway Tolls (IOI18_highway) C++17
51 / 100
 683 ms 71292 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) {
	askcnt++;
	assert(askcnt <= 90);
	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) {
	askcnt++;
	assert(askcnt <= 90);
	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 15 ms 27720 KB Output is correct
2 Correct 14 ms 27672 KB Output is correct
3 Correct 13 ms 27656 KB Output is correct
4 Correct 12 ms 27676 KB Output is correct
5 Correct 13 ms 27652 KB Output is correct
6 Correct 13 ms 27692 KB Output is correct
7 Correct 14 ms 27708 KB Output is correct
8 Correct 13 ms 27728 KB Output is correct
9 Correct 14 ms 27676 KB Output is correct
10 Correct 14 ms 27740 KB Output is correct
11 Correct 13 ms 27636 KB Output is correct
12 Correct 14 ms 27672 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 27808 KB Output is correct
2 Correct 22 ms 28496 KB Output is correct
3 Correct 129 ms 34720 KB Output is correct
4 Correct 136 ms 34720 KB Output is correct
5 Correct 107 ms 34732 KB Output is correct
6 Correct 126 ms 34720 KB Output is correct
7 Correct 145 ms 34744 KB Output is correct
8 Correct 149 ms 34764 KB Output is correct
9 Correct 120 ms 34708 KB Output is correct
10 Correct 109 ms 34724 KB Output is correct
11 Correct 111 ms 36296 KB Output is correct
12 Correct 118 ms 37364 KB Output is correct
13 Correct 140 ms 36472 KB Output is correct
14 Correct 137 ms 36588 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 29300 KB Output is correct
2 Correct 27 ms 30900 KB Output is correct
3 Correct 46 ms 32516 KB Output is correct
4 Correct 105 ms 41640 KB Output is correct
5 Correct 118 ms 41636 KB Output is correct
6 Correct 139 ms 41704 KB Output is correct
7 Correct 92 ms 41632 KB Output is correct
8 Correct 137 ms 41636 KB Output is correct
9 Correct 91 ms 41748 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 27708 KB Output is correct
2 Correct 25 ms 28540 KB Output is correct
3 Correct 90 ms 33288 KB Output is correct
4 Correct 125 ms 34824 KB Output is correct
5 Correct 115 ms 34724 KB Output is correct
6 Correct 138 ms 34724 KB Output is correct
7 Correct 152 ms 34760 KB Output is correct
8 Correct 117 ms 34720 KB Output is correct
9 Correct 144 ms 34720 KB Output is correct
10 Correct 153 ms 34736 KB Output is correct
11 Correct 134 ms 35928 KB Output is correct
12 Correct 127 ms 37264 KB Output is correct
13 Correct 139 ms 36628 KB Output is correct
14 Correct 136 ms 37080 KB Output is correct
15 Correct 130 ms 34728 KB Output is correct
16 Correct 124 ms 34788 KB Output is correct
17 Correct 123 ms 36748 KB Output is correct
18 Correct 132 ms 36968 KB Output is correct
19 Correct 122 ms 34744 KB Output is correct
20 Correct 116 ms 37672 KB Output is correct
21 Correct 132 ms 35104 KB Output is correct
22 Correct 118 ms 35080 KB Output is correct
23 Correct 114 ms 35088 KB Output is correct
24 Correct 117 ms 35736 KB Output is correct
25 Correct 125 ms 40924 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 28564 KB Output is correct
2 Incorrect 53 ms 28568 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 28588 KB Output is correct
2 Correct 30 ms 28624 KB Output is correct
3 Correct 300 ms 35148 KB Output is correct
4 Runtime error 683 ms 71292 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -