oj.uz

Submission #794156

# Submission time Handle Problem Language Result Execution time Memory
794156 2023-07-26T09:59:06 Z Sohsoh84 Highway Tolls (IOI18_highway) C++17
51 / 100
 544 ms 42452 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;

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

	for (int e : dfs_order) cerr << e << sep;
	cerr << endl;

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

	int mn = get({});
	while (true) {
		vector<int> tmp = random_spt();
		if (getp(tmp) == mn) {
			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 14 ms 27728 KB Output is correct
2 Correct 14 ms 27672 KB Output is correct
3 Correct 14 ms 27704 KB Output is correct
4 Correct 14 ms 27740 KB Output is correct
5 Correct 14 ms 27656 KB Output is correct
6 Correct 14 ms 27744 KB Output is correct
7 Correct 17 ms 27668 KB Output is correct
8 Correct 17 ms 27672 KB Output is correct
9 Correct 17 ms 27708 KB Output is correct
10 Correct 13 ms 27672 KB Output is correct
11 Correct 14 ms 27728 KB Output is correct
12 Correct 14 ms 27692 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 27728 KB Output is correct
2 Correct 63 ms 28568 KB Output is correct
3 Correct 466 ms 35464 KB Output is correct
4 Correct 495 ms 35488 KB Output is correct
5 Correct 491 ms 35440 KB Output is correct
6 Correct 514 ms 35556 KB Output is correct
7 Correct 468 ms 35416 KB Output is correct
8 Correct 489 ms 35416 KB Output is correct
9 Correct 509 ms 35436 KB Output is correct
10 Correct 500 ms 35548 KB Output is correct
11 Correct 520 ms 37016 KB Output is correct
12 Correct 506 ms 38112 KB Output is correct
13 Correct 480 ms 37180 KB Output is correct
14 Correct 492 ms 37316 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 29376 KB Output is correct
2 Correct 134 ms 30980 KB Output is correct
3 Correct 168 ms 32536 KB Output is correct
4 Correct 468 ms 42340 KB Output is correct
5 Correct 508 ms 42352 KB Output is correct
6 Correct 482 ms 42348 KB Output is correct
7 Correct 451 ms 42268 KB Output is correct
8 Correct 483 ms 42452 KB Output is correct
9 Correct 449 ms 42292 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 27812 KB Output is correct
2 Correct 66 ms 28556 KB Output is correct
3 Correct 379 ms 33848 KB Output is correct
4 Correct 513 ms 35428 KB Output is correct
5 Correct 487 ms 35528 KB Output is correct
6 Correct 475 ms 35428 KB Output is correct
7 Correct 496 ms 35512 KB Output is correct
8 Correct 485 ms 35536 KB Output is correct
9 Correct 480 ms 35516 KB Output is correct
10 Correct 502 ms 35424 KB Output is correct
11 Correct 530 ms 36560 KB Output is correct
12 Correct 529 ms 37984 KB Output is correct
13 Correct 498 ms 37340 KB Output is correct
14 Correct 528 ms 37872 KB Output is correct
15 Correct 492 ms 35436 KB Output is correct
16 Correct 472 ms 35504 KB Output is correct
17 Correct 537 ms 37456 KB Output is correct
18 Correct 499 ms 37592 KB Output is correct
19 Correct 464 ms 35444 KB Output is correct
20 Correct 514 ms 38444 KB Output is correct
21 Correct 485 ms 35672 KB Output is correct
22 Correct 493 ms 35668 KB Output is correct
23 Correct 504 ms 35792 KB Output is correct
24 Correct 472 ms 36452 KB Output is correct
25 Correct 544 ms 41636 KB Output is correct

Subtask #5
0 / 18.0

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