oj.uz

Submission #799458

# Submission time Handle Problem Language Result Execution time Memory
799458 2023-07-31T14:47:38 Z Sohsoh84 Highway Tolls (IOI18_highway) C++17
23 / 100
 614 ms 43580 KB 
#include "highway.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#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;
ll from[MAXN], to[MAXN], n, m, par[MAXN], mn;
vector<int> adj[MAXN], dfs_order, fuck, jahel;
ll fucking_root, A, B;

inline int f(int ind, int v) {
	return from[ind] ^ to[ind] ^ v;
}

void dfs(int v, int p, int d = 0) {
	dfs_order.push_back(v);

	if (d == mn / A)
		jahel.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, d + 1);
	}
}


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, int tof = 0) {
	par[root] = -1;
	dfs_order.clear();
	jahel.clear();

	dfs(root, root);

	debug(root)
	jahel.insert(jahel.begin(), 0);

	int l = 1, r = int(dfs_order.size()) - 1;
	//tof = 0;
	if (tof) r = int(jahel.size()) - 1;

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

	while (l < r) {
		int mid = (l + r) >> 1;
		int tmid = mid;
		if (tof) {
			tmid = 1;
			while (dfs_order[tmid] != jahel[mid]) tmid++;
			assert(jahel[mid] == dfs_order[tmid]);
		}

		if (getp(1, tmid) == mn) r = mid;
		else l = mid + 1;
	}

	return (tof ? jahel[l] : dfs_order[l]);

}

int dist[MAXN];

const double Z = 0.45;

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;
	A = A_;
	B = B_;

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

	cerr << u << sep << v << endl;

	answer(u, v);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 27728 KB Output is correct
2 Correct 16 ms 27680 KB Output is correct
3 Correct 15 ms 27660 KB Output is correct
4 Correct 15 ms 27660 KB Output is correct
5 Correct 15 ms 27728 KB Output is correct
6 Correct 15 ms 27728 KB Output is correct
7 Correct 15 ms 27728 KB Output is correct
8 Correct 15 ms 27728 KB Output is correct
9 Correct 15 ms 27728 KB Output is correct
10 Correct 17 ms 27668 KB Output is correct
11 Correct 16 ms 27680 KB Output is correct
12 Correct 15 ms 27716 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 27748 KB Output is correct
2 Correct 63 ms 28756 KB Output is correct
3 Correct 513 ms 37240 KB Output is correct
4 Correct 512 ms 37124 KB Output is correct
5 Correct 475 ms 37204 KB Output is correct
6 Correct 517 ms 36960 KB Output is correct
7 Correct 489 ms 37276 KB Output is correct
8 Correct 482 ms 37340 KB Output is correct
9 Correct 505 ms 37456 KB Output is correct
10 Correct 494 ms 37316 KB Output is correct
11 Correct 496 ms 38620 KB Output is correct
12 Correct 479 ms 39584 KB Output is correct
13 Correct 519 ms 38640 KB Output is correct
14 Incorrect 511 ms 39124 KB Output is incorrect: {s, t} is wrong.
15 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 29432 KB Output is correct
2 Correct 104 ms 30892 KB Output is correct
3 Correct 48 ms 30344 KB Output is correct
4 Correct 343 ms 40328 KB Output is correct
5 Correct 313 ms 40504 KB Output is correct
6 Correct 403 ms 41828 KB Output is correct
7 Correct 103 ms 34748 KB Output is correct
8 Correct 343 ms 41112 KB Output is correct
9 Incorrect 476 ms 43580 KB Output is incorrect: {s, t} is wrong.
10 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 27728 KB Output is correct
2 Correct 66 ms 28676 KB Output is correct
3 Correct 250 ms 34468 KB Output is correct
4 Correct 237 ms 35760 KB Output is correct
5 Correct 383 ms 36684 KB Output is correct
6 Correct 108 ms 34832 KB Output is correct
7 Correct 290 ms 36016 KB Output is correct
8 Correct 274 ms 35744 KB Output is correct
9 Incorrect 496 ms 37156 KB Output is incorrect: {s, t} is wrong.
10 Halted 0 ms 0 KB -

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 28720 KB Output is correct
2 Correct 70 ms 28896 KB Output is correct
3 Correct 474 ms 37472 KB Output is correct
4 Correct 473 ms 37792 KB Output is correct
5 Correct 543 ms 39212 KB Output is correct
6 Correct 522 ms 38756 KB Output is correct
7 Correct 519 ms 39056 KB Output is correct
8 Correct 506 ms 38964 KB Output is correct
9 Correct 207 ms 34880 KB Output is correct
10 Correct 184 ms 35284 KB Output is correct
11 Correct 163 ms 35084 KB Output is correct
12 Correct 390 ms 38172 KB Output is correct
13 Correct 526 ms 38796 KB Output is correct
14 Correct 502 ms 38632 KB Output is correct
15 Correct 529 ms 38652 KB Output is correct
16 Correct 300 ms 36968 KB Output is correct
17 Correct 436 ms 37564 KB Output is correct
18 Correct 402 ms 37168 KB Output is correct
19 Correct 491 ms 37752 KB Output is correct
20 Correct 309 ms 36868 KB Output is correct
21 Correct 596 ms 39072 KB Output is correct

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 28836 KB Output is correct
2 Correct 69 ms 28856 KB Output is correct
3 Correct 427 ms 37236 KB Output is correct
4 Correct 489 ms 37608 KB Output is correct
5 Correct 480 ms 37608 KB Output is correct
6 Correct 540 ms 39244 KB Output is correct
7 Correct 498 ms 37408 KB Output is correct
8 Correct 594 ms 37824 KB Output is correct
9 Correct 582 ms 38064 KB Output is correct
10 Correct 614 ms 39296 KB Output is correct
11 Correct 532 ms 38792 KB Output is correct
12 Correct 593 ms 39052 KB Output is correct
13 Correct 207 ms 35252 KB Output is correct
14 Correct 249 ms 35832 KB Output is correct
15 Correct 252 ms 35752 KB Output is correct
16 Correct 196 ms 35688 KB Output is correct
17 Correct 142 ms 35024 KB Output is correct
18 Correct 219 ms 36016 KB Output is correct
19 Correct 415 ms 38092 KB Output is correct
20 Correct 486 ms 38248 KB Output is correct
21 Correct 499 ms 38720 KB Output is correct
22 Correct 471 ms 38432 KB Output is correct
23 Correct 549 ms 39068 KB Output is correct
24 Correct 589 ms 38788 KB Output is correct
25 Correct 402 ms 38060 KB Output is correct
26 Correct 546 ms 39380 KB Output is correct
27 Correct 388 ms 36928 KB Output is correct
28 Correct 351 ms 36940 KB Output is correct
29 Correct 340 ms 36972 KB Output is correct
30 Incorrect 495 ms 37196 KB Output is incorrect: {s, t} is wrong.
31 Halted 0 ms 0 KB -