oj.uz

Submission #799412

# Submission time Handle Problem Language Result Execution time Memory
799412 2023-07-31T13:57:09 Z Sohsoh84 Highway Tolls (IOI18_highway) C++17
51 / 100
 199 ms 42032 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.3;

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

		if (v < fucking_root) continue;

		for (int ind : adj[v]) {
			int u = f(ind, v);
			if (u < fucking_root) continue;
			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 15 ms 27684 KB Output is correct
2 Correct 14 ms 27676 KB Output is correct
3 Correct 14 ms 27652 KB Output is correct
4 Correct 14 ms 27672 KB Output is correct
5 Correct 16 ms 27668 KB Output is correct
6 Correct 13 ms 27744 KB Output is correct
7 Correct 12 ms 27668 KB Output is correct
8 Correct 12 ms 27624 KB Output is correct
9 Correct 12 ms 27728 KB Output is correct
10 Correct 11 ms 27728 KB Output is correct
11 Correct 12 ms 27728 KB Output is correct
12 Correct 12 ms 27688 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 27796 KB Output is correct
2 Correct 36 ms 28580 KB Output is correct
3 Correct 144 ms 35140 KB Output is correct
4 Correct 138 ms 35120 KB Output is correct
5 Correct 109 ms 34984 KB Output is correct
6 Correct 156 ms 35076 KB Output is correct
7 Correct 145 ms 35080 KB Output is correct
8 Correct 119 ms 34960 KB Output is correct
9 Correct 124 ms 35084 KB Output is correct
10 Correct 151 ms 35080 KB Output is correct
11 Correct 136 ms 36616 KB Output is correct
12 Correct 151 ms 37596 KB Output is correct
13 Correct 162 ms 36744 KB Output is correct
14 Correct 175 ms 36744 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 29216 KB Output is correct
2 Correct 30 ms 30600 KB Output is correct
3 Correct 36 ms 30048 KB Output is correct
4 Correct 101 ms 38676 KB Output is correct
5 Correct 88 ms 38752 KB Output is correct
6 Correct 111 ms 40396 KB Output is correct
7 Correct 91 ms 33928 KB Output is correct
8 Correct 116 ms 39604 KB Output is correct
9 Correct 122 ms 42032 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 29 ms 28580 KB Output is correct
3 Correct 125 ms 33348 KB Output is correct
4 Correct 126 ms 34260 KB Output is correct
5 Correct 128 ms 34696 KB Output is correct
6 Correct 119 ms 33808 KB Output is correct
7 Correct 128 ms 34512 KB Output is correct
8 Correct 123 ms 34352 KB Output is correct
9 Correct 136 ms 35192 KB Output is correct
10 Correct 126 ms 34996 KB Output is correct
11 Correct 166 ms 36200 KB Output is correct
12 Correct 127 ms 37512 KB Output is correct
13 Correct 145 ms 36908 KB Output is correct
14 Correct 130 ms 37424 KB Output is correct
15 Correct 118 ms 35000 KB Output is correct
16 Correct 130 ms 34204 KB Output is correct
17 Correct 116 ms 35956 KB Output is correct
18 Correct 105 ms 35252 KB Output is correct
19 Correct 85 ms 33652 KB Output is correct
20 Correct 101 ms 34124 KB Output is correct
21 Correct 102 ms 35044 KB Output is correct
22 Correct 119 ms 34548 KB Output is correct
23 Correct 113 ms 35436 KB Output is correct
24 Correct 132 ms 36088 KB Output is correct
25 Correct 135 ms 41240 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 28604 KB Output is correct
2 Correct 30 ms 28624 KB Output is correct
3 Correct 133 ms 35380 KB Output is correct
4 Correct 154 ms 35612 KB Output is correct
5 Correct 199 ms 36752 KB Output is correct
6 Incorrect 186 ms 36360 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 28552 KB Output is correct
2 Correct 32 ms 28644 KB Output is correct
3 Correct 153 ms 35280 KB Output is correct
4 Correct 170 ms 35448 KB Output is correct
5 Incorrect 179 ms 35540 KB Output isn't correct
6 Halted 0 ms 0 KB -