oj.uz

Submission #799443

# Submission time Handle Problem Language Result Execution time Memory
799443 2023-07-31T14:33:50 Z Sohsoh84 Highway Tolls (IOI18_highway) C++17
23 / 100
 570 ms 42468 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, jahel;
int 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;
	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 = 0;
			while (dfs_order[tmid] != jahel[mid]) 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 14 ms 27684 KB Output is correct
3 Correct 17 ms 27728 KB Output is correct
4 Correct 14 ms 27728 KB Output is correct
5 Correct 14 ms 27680 KB Output is correct
6 Correct 18 ms 27692 KB Output is correct
7 Correct 14 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 14 ms 27728 KB Output is correct
11 Correct 15 ms 27672 KB Output is correct
12 Correct 14 ms 27744 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 27732 KB Output is correct
2 Correct 76 ms 28584 KB Output is correct
3 Correct 494 ms 36180 KB Output is correct
4 Correct 570 ms 35948 KB Output is correct
5 Correct 493 ms 36176 KB Output is correct
6 Correct 512 ms 35900 KB Output is correct
7 Correct 506 ms 36200 KB Output is correct
8 Correct 519 ms 36128 KB Output is correct
9 Correct 509 ms 36212 KB Output is correct
10 Correct 501 ms 36196 KB Output is correct
11 Correct 527 ms 37708 KB Output is correct
12 Correct 521 ms 38448 KB Output is correct
13 Correct 501 ms 37568 KB Output is correct
14 Incorrect 513 ms 37964 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 65 ms 29304 KB Output is correct
2 Correct 103 ms 30672 KB Output is correct
3 Correct 47 ms 30072 KB Output is correct
4 Correct 334 ms 39408 KB Output is correct
5 Correct 309 ms 39520 KB Output is correct
6 Correct 384 ms 40792 KB Output is correct
7 Correct 108 ms 33980 KB Output is correct
8 Correct 378 ms 40212 KB Output is correct
9 Incorrect 471 ms 42468 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 27740 KB Output is correct
2 Correct 63 ms 28684 KB Output is correct
3 Correct 266 ms 33652 KB Output is correct
4 Correct 230 ms 34860 KB Output is correct
5 Correct 392 ms 35572 KB Output is correct
6 Correct 111 ms 33884 KB Output is correct
7 Correct 287 ms 34920 KB Output is correct
8 Correct 241 ms 34732 KB Output is correct
9 Incorrect 476 ms 36068 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 28692 KB Output is correct
2 Correct 76 ms 28748 KB Output is correct
3 Correct 480 ms 36344 KB Output is correct
4 Correct 460 ms 36564 KB Output is correct
5 Correct 519 ms 37752 KB Output is correct
6 Correct 488 ms 37196 KB Output is correct
7 Correct 519 ms 37524 KB Output is correct
8 Correct 544 ms 37388 KB Output is correct
9 Correct 218 ms 33788 KB Output is correct
10 Correct 161 ms 34232 KB Output is correct
11 Correct 174 ms 34012 KB Output is correct
12 Correct 430 ms 36720 KB Output is correct
13 Correct 501 ms 37396 KB Output is correct
14 Correct 522 ms 37332 KB Output is correct
15 Correct 568 ms 37392 KB Output is correct
16 Correct 301 ms 35776 KB Output is correct
17 Correct 446 ms 36500 KB Output is correct
18 Correct 409 ms 36120 KB Output is correct
19 Correct 536 ms 36700 KB Output is correct
20 Correct 303 ms 35828 KB Output is correct
21 Correct 529 ms 37688 KB Output is correct

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 28724 KB Output is correct
2 Correct 64 ms 28728 KB Output is correct
3 Correct 451 ms 36156 KB Output is correct
4 Correct 470 ms 36404 KB Output is correct
5 Correct 460 ms 36436 KB Output is correct
6 Correct 543 ms 37924 KB Output is correct
7 Correct 448 ms 36304 KB Output is correct
8 Correct 549 ms 36700 KB Output is correct
9 Correct 506 ms 36908 KB Output is correct
10 Correct 537 ms 37856 KB Output is correct
11 Correct 539 ms 37448 KB Output is correct
12 Correct 531 ms 37788 KB Output is correct
13 Correct 215 ms 34144 KB Output is correct
14 Correct 215 ms 34740 KB Output is correct
15 Correct 248 ms 34620 KB Output is correct
16 Correct 218 ms 34656 KB Output is correct
17 Correct 164 ms 33972 KB Output is correct
18 Correct 262 ms 34888 KB Output is correct
19 Correct 496 ms 36784 KB Output is correct
20 Correct 492 ms 37004 KB Output is correct
21 Correct 537 ms 37564 KB Output is correct
22 Correct 508 ms 37012 KB Output is correct
23 Correct 539 ms 37636 KB Output is correct
24 Correct 531 ms 37348 KB Output is correct
25 Correct 351 ms 36732 KB Output is correct
26 Correct 565 ms 37856 KB Output is correct
27 Correct 346 ms 35892 KB Output is correct
28 Correct 375 ms 36028 KB Output is correct
29 Correct 315 ms 36016 KB Output is correct
30 Incorrect 480 ms 36144 KB Output is incorrect: {s, t} is wrong.
31 Halted 0 ms 0 KB -