oj.uz

Submission #794106

# Submission time Handle Problem Language Result Execution time Memory
794106 2023-07-26T09:23:27 Z Sohsoh84 Highway Tolls (IOI18_highway) C++17
51 / 100
 555 ms 262144 KB 
#include "highway.h"
#include <bits/stdc++.h>

using namespace std;

#define sep		' '
#define debug(x)	cerr << #x << ": " << x << endl;

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

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 < n - 1; i++) {
		from[i] = U[i];
		to[i] = V[i];

		adj[from[i]].push_back(i);
		adj[to[i]].push_back(i);
	}

	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 13 ms 23760 KB Output is correct
2 Correct 14 ms 23812 KB Output is correct
3 Correct 12 ms 23824 KB Output is correct
4 Correct 14 ms 23816 KB Output is correct
5 Correct 12 ms 23760 KB Output is correct
6 Correct 18 ms 23704 KB Output is correct
7 Correct 13 ms 23760 KB Output is correct
8 Correct 13 ms 23760 KB Output is correct
9 Correct 15 ms 23824 KB Output is correct
10 Correct 13 ms 23760 KB Output is correct
11 Correct 14 ms 23752 KB Output is correct
12 Correct 13 ms 23760 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23888 KB Output is correct
2 Correct 58 ms 24604 KB Output is correct
3 Correct 472 ms 31476 KB Output is correct
4 Correct 473 ms 31468 KB Output is correct
5 Correct 464 ms 31472 KB Output is correct
6 Correct 466 ms 31468 KB Output is correct
7 Correct 511 ms 31472 KB Output is correct
8 Correct 463 ms 31472 KB Output is correct
9 Correct 510 ms 31756 KB Output is correct
10 Correct 462 ms 31480 KB Output is correct
11 Correct 467 ms 33068 KB Output is correct
12 Correct 500 ms 34108 KB Output is correct
13 Correct 450 ms 33240 KB Output is correct
14 Correct 486 ms 33532 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 25436 KB Output is correct
2 Correct 112 ms 27020 KB Output is correct
3 Correct 160 ms 28604 KB Output is correct
4 Correct 419 ms 38420 KB Output is correct
5 Correct 426 ms 38436 KB Output is correct
6 Correct 458 ms 38456 KB Output is correct
7 Correct 421 ms 38392 KB Output is correct
8 Correct 463 ms 38416 KB Output is correct
9 Correct 438 ms 38436 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23888 KB Output is correct
2 Correct 62 ms 24564 KB Output is correct
3 Correct 365 ms 29896 KB Output is correct
4 Correct 455 ms 31480 KB Output is correct
5 Correct 497 ms 31472 KB Output is correct
6 Correct 488 ms 31512 KB Output is correct
7 Correct 555 ms 31476 KB Output is correct
8 Correct 456 ms 31468 KB Output is correct
9 Correct 499 ms 31456 KB Output is correct
10 Correct 484 ms 31476 KB Output is correct
11 Correct 522 ms 32628 KB Output is correct
12 Correct 515 ms 33940 KB Output is correct
13 Correct 480 ms 33408 KB Output is correct
14 Correct 465 ms 33868 KB Output is correct
15 Correct 500 ms 31472 KB Output is correct
16 Correct 448 ms 31484 KB Output is correct
17 Correct 479 ms 33456 KB Output is correct
18 Correct 489 ms 33656 KB Output is correct
19 Correct 469 ms 31564 KB Output is correct
20 Correct 462 ms 34460 KB Output is correct
21 Correct 512 ms 31676 KB Output is correct
22 Correct 481 ms 31712 KB Output is correct
23 Correct 501 ms 31800 KB Output is correct
24 Correct 454 ms 32480 KB Output is correct
25 Correct 495 ms 37684 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 220 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 265 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -