oj.uz

Submission #799397

# Submission time Handle Problem Language Result Execution time Memory
799397 2023-07-31T13:48:18 Z Sohsoh84 Highway Tolls (IOI18_highway) C++17
51 / 100
 193 ms 41984 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;

bool bad[MAXN];
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;
		if (bad[u]) 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];

}

int dist[MAXN];

const double Z = 0.4;

int fucking_root;

inline vector<int> random_spt() {
	vector<int> ans;
	queue<int> q;

	int l = 0, r = n - 1;
	while (l < r) {
		int len = r - l;
		int mid = l + Z * len;
		mid = max(mid, l);
		mid = min(mid, r - 1);

		vector<int> W(m);
	
		for (int i = 0; i < m; i++)
			if (from[i] <= mid || to[i] <= mid)
				W[i] = 1;

		if (ask(W) == mn) {
			for (int i = l; i <= mid; i++) bad[i] = true;
			l = mid + 1;
		} else r = mid;
	}

	int v = l;
	fucking_root = v;
	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({});
	vector<int> tmp = random_spt();

	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);
	}


	int v = find(fucking_root);
	int u = find(v);
	
	cerr << u << sep << v << endl;

	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 27784 KB Output is correct
3 Correct 15 ms 27692 KB Output is correct
4 Correct 15 ms 27728 KB Output is correct
5 Correct 14 ms 27744 KB Output is correct
6 Correct 14 ms 27728 KB Output is correct
7 Correct 14 ms 27660 KB Output is correct
8 Correct 14 ms 27724 KB Output is correct
9 Correct 16 ms 27676 KB Output is correct
10 Correct 15 ms 27732 KB Output is correct
11 Correct 15 ms 27728 KB Output is correct
12 Correct 14 ms 27676 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 27808 KB Output is correct
2 Correct 25 ms 28484 KB Output is correct
3 Correct 123 ms 35108 KB Output is correct
4 Correct 130 ms 35052 KB Output is correct
5 Correct 129 ms 35072 KB Output is correct
6 Correct 111 ms 35084 KB Output is correct
7 Correct 140 ms 35252 KB Output is correct
8 Correct 131 ms 35060 KB Output is correct
9 Correct 134 ms 35072 KB Output is correct
10 Correct 108 ms 35088 KB Output is correct
11 Correct 114 ms 36544 KB Output is correct
12 Correct 117 ms 37744 KB Output is correct
13 Correct 121 ms 36764 KB Output is correct
14 Correct 137 ms 36780 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 29128 KB Output is correct
2 Correct 29 ms 30612 KB Output is correct
3 Correct 40 ms 30248 KB Output is correct
4 Correct 85 ms 38836 KB Output is correct
5 Correct 88 ms 38912 KB Output is correct
6 Correct 136 ms 40460 KB Output is correct
7 Correct 79 ms 34360 KB Output is correct
8 Correct 87 ms 39692 KB Output is correct
9 Correct 88 ms 41984 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 103 ms 33396 KB Output is correct
4 Correct 120 ms 34428 KB Output is correct
5 Correct 116 ms 34704 KB Output is correct
6 Correct 97 ms 34372 KB Output is correct
7 Correct 117 ms 34680 KB Output is correct
8 Correct 98 ms 34556 KB Output is correct
9 Correct 134 ms 35080 KB Output is correct
10 Correct 108 ms 35020 KB Output is correct
11 Correct 149 ms 36200 KB Output is correct
12 Correct 117 ms 37500 KB Output is correct
13 Correct 120 ms 37044 KB Output is correct
14 Correct 146 ms 37384 KB Output is correct
15 Correct 105 ms 34968 KB Output is correct
16 Correct 97 ms 34428 KB Output is correct
17 Correct 116 ms 36032 KB Output is correct
18 Correct 117 ms 35536 KB Output is correct
19 Correct 90 ms 34160 KB Output is correct
20 Correct 126 ms 34556 KB Output is correct
21 Correct 97 ms 35048 KB Output is correct
22 Correct 103 ms 34824 KB Output is correct
23 Correct 95 ms 35416 KB Output is correct
24 Correct 120 ms 36092 KB Output is correct
25 Correct 127 ms 41240 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 28468 KB Output is correct
2 Correct 30 ms 28652 KB Output is correct
3 Correct 143 ms 34664 KB Output is correct
4 Correct 167 ms 35388 KB Output is correct
5 Correct 193 ms 36384 KB Output is correct
6 Correct 173 ms 35992 KB Output is correct
7 Correct 192 ms 36424 KB Output is correct
8 Correct 184 ms 36388 KB Output is correct
9 Incorrect 145 ms 33820 KB Output is incorrect: {s, t} is wrong.
10 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 28636 KB Output is correct
2 Correct 26 ms 28744 KB Output is correct
3 Correct 104 ms 34844 KB Output is correct
4 Correct 162 ms 35204 KB Output is correct
5 Correct 150 ms 35220 KB Output is correct
6 Correct 147 ms 36524 KB Output is correct
7 Correct 132 ms 34960 KB Output is correct
8 Correct 141 ms 35596 KB Output is correct
9 Correct 151 ms 35756 KB Output is correct
10 Correct 156 ms 36808 KB Output is correct
11 Incorrect 174 ms 36016 KB Output is incorrect: {s, t} is wrong.
12 Halted 0 ms 0 KB -