oj.uz

Submission #797393

# Submission time Handle Problem Language Result Execution time Memory
797393 2023-07-29T10:19:39 Z Sohsoh84 Highway Tolls (IOI18_highway) C++17
51 / 100
 171 ms 42000 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];

}

int dist[MAXN];

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

	int l = 0, r = n - 1;
	while (l < r) {
		int mid = (l + 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) == mid) l = mid + 1;
		else r = mid;
	}

	int v = l;
	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(0);
	int u = find(v);

	answer(u, v);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 27728 KB Output is correct
2 Correct 15 ms 27688 KB Output is correct
3 Correct 15 ms 27620 KB Output is correct
4 Correct 16 ms 27728 KB Output is correct
5 Correct 16 ms 27728 KB Output is correct
6 Correct 16 ms 27672 KB Output is correct
7 Correct 15 ms 27672 KB Output is correct
8 Correct 14 ms 27684 KB Output is correct
9 Correct 16 ms 27600 KB Output is correct
10 Correct 15 ms 27672 KB Output is correct
11 Correct 17 ms 27672 KB Output is correct
12 Correct 16 ms 27632 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 27796 KB Output is correct
2 Correct 24 ms 28580 KB Output is correct
3 Correct 115 ms 35060 KB Output is correct
4 Correct 154 ms 34960 KB Output is correct
5 Correct 136 ms 35056 KB Output is correct
6 Correct 152 ms 35076 KB Output is correct
7 Correct 138 ms 35072 KB Output is correct
8 Correct 141 ms 35052 KB Output is correct
9 Correct 133 ms 35060 KB Output is correct
10 Correct 126 ms 35068 KB Output is correct
11 Correct 149 ms 36552 KB Output is correct
12 Correct 142 ms 37580 KB Output is correct
13 Correct 132 ms 36748 KB Output is correct
14 Correct 139 ms 36776 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 29252 KB Output is correct
2 Correct 29 ms 30964 KB Output is correct
3 Correct 39 ms 32608 KB Output is correct
4 Correct 126 ms 41984 KB Output is correct
5 Correct 111 ms 41968 KB Output is correct
6 Correct 123 ms 41952 KB Output is correct
7 Correct 112 ms 41984 KB Output is correct
8 Correct 119 ms 41976 KB Output is correct
9 Correct 108 ms 42000 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 27736 KB Output is correct
2 Correct 25 ms 28584 KB Output is correct
3 Correct 123 ms 33560 KB Output is correct
4 Correct 149 ms 35064 KB Output is correct
5 Correct 141 ms 34980 KB Output is correct
6 Correct 143 ms 35072 KB Output is correct
7 Correct 171 ms 35080 KB Output is correct
8 Correct 139 ms 35044 KB Output is correct
9 Correct 140 ms 35084 KB Output is correct
10 Correct 143 ms 34956 KB Output is correct
11 Correct 165 ms 36184 KB Output is correct
12 Correct 163 ms 37500 KB Output is correct
13 Correct 140 ms 36908 KB Output is correct
14 Correct 155 ms 37356 KB Output is correct
15 Correct 148 ms 35060 KB Output is correct
16 Correct 134 ms 34968 KB Output is correct
17 Correct 148 ms 37124 KB Output is correct
18 Correct 170 ms 37204 KB Output is correct
19 Correct 142 ms 35088 KB Output is correct
20 Correct 147 ms 38004 KB Output is correct
21 Correct 119 ms 35292 KB Output is correct
22 Correct 113 ms 35284 KB Output is correct
23 Correct 117 ms 35428 KB Output is correct
24 Correct 152 ms 36068 KB Output is correct
25 Correct 159 ms 41252 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 28608 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 26 ms 28600 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -