oj.uz

Submission #799447

# Submission time Handle Problem Language Result Execution time Memory
799447 2023-07-31T14:37:28 Z Sohsoh84 Highway Tolls (IOI18_highway) C++17
23 / 100
 588 ms 42516 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 = 1;
			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 14 ms 27728 KB Output is correct
2 Correct 14 ms 27744 KB Output is correct
3 Correct 17 ms 27728 KB Output is correct
4 Correct 15 ms 27636 KB Output is correct
5 Correct 14 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 14 ms 27680 KB Output is correct
9 Correct 15 ms 27680 KB Output is correct
10 Correct 17 ms 27728 KB Output is correct
11 Correct 14 ms 27628 KB Output is correct
12 Correct 14 ms 27736 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 27712 KB Output is correct
2 Correct 66 ms 28584 KB Output is correct
3 Correct 506 ms 36180 KB Output is correct
4 Correct 511 ms 36012 KB Output is correct
5 Correct 488 ms 36200 KB Output is correct
6 Correct 480 ms 35900 KB Output is correct
7 Correct 484 ms 36224 KB Output is correct
8 Correct 485 ms 36172 KB Output is correct
9 Correct 500 ms 36312 KB Output is correct
10 Correct 485 ms 36272 KB Output is correct
11 Correct 491 ms 37672 KB Output is correct
12 Correct 538 ms 38448 KB Output is correct
13 Correct 492 ms 37516 KB Output is correct
14 Incorrect 497 ms 37948 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 63 ms 29308 KB Output is correct
2 Correct 94 ms 30764 KB Output is correct
3 Correct 59 ms 30072 KB Output is correct
4 Correct 341 ms 39468 KB Output is correct
5 Correct 318 ms 39680 KB Output is correct
6 Correct 397 ms 40872 KB Output is correct
7 Correct 109 ms 34096 KB Output is correct
8 Correct 373 ms 40232 KB Output is correct
9 Incorrect 491 ms 42516 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 18 ms 27728 KB Output is correct
2 Correct 65 ms 28652 KB Output is correct
3 Correct 273 ms 33744 KB Output is correct
4 Correct 213 ms 34676 KB Output is correct
5 Correct 359 ms 35692 KB Output is correct
6 Correct 85 ms 33816 KB Output is correct
7 Correct 253 ms 35008 KB Output is correct
8 Correct 256 ms 34676 KB Output is correct
9 Incorrect 511 ms 36148 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 63 ms 28612 KB Output is correct
2 Correct 66 ms 28800 KB Output is correct
3 Correct 478 ms 36344 KB Output is correct
4 Correct 486 ms 36612 KB Output is correct
5 Correct 547 ms 37696 KB Output is correct
6 Correct 489 ms 37260 KB Output is correct
7 Correct 514 ms 37628 KB Output is correct
8 Correct 558 ms 37492 KB Output is correct
9 Correct 209 ms 33844 KB Output is correct
10 Correct 141 ms 34208 KB Output is correct
11 Correct 186 ms 34120 KB Output is correct
12 Correct 420 ms 36728 KB Output is correct
13 Correct 516 ms 37608 KB Output is correct
14 Correct 553 ms 37340 KB Output is correct
15 Correct 568 ms 37300 KB Output is correct
16 Correct 312 ms 35780 KB Output is correct
17 Correct 431 ms 36512 KB Output is correct
18 Correct 411 ms 36120 KB Output is correct
19 Correct 466 ms 36740 KB Output is correct
20 Correct 302 ms 35832 KB Output is correct
21 Correct 523 ms 37832 KB Output is correct

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 28716 KB Output is correct
2 Correct 66 ms 28628 KB Output is correct
3 Correct 472 ms 36080 KB Output is correct
4 Correct 505 ms 36440 KB Output is correct
5 Correct 455 ms 36620 KB Output is correct
6 Correct 579 ms 38056 KB Output is correct
7 Correct 452 ms 36304 KB Output is correct
8 Correct 498 ms 36612 KB Output is correct
9 Correct 581 ms 36800 KB Output is correct
10 Correct 588 ms 37856 KB Output is correct
11 Correct 549 ms 37460 KB Output is correct
12 Correct 557 ms 37700 KB Output is correct
13 Correct 178 ms 34128 KB Output is correct
14 Correct 243 ms 34720 KB Output is correct
15 Correct 271 ms 34620 KB Output is correct
16 Correct 223 ms 34676 KB Output is correct
17 Correct 157 ms 33952 KB Output is correct
18 Correct 256 ms 34972 KB Output is correct
19 Correct 479 ms 36716 KB Output is correct
20 Correct 471 ms 36892 KB Output is correct
21 Correct 483 ms 37380 KB Output is correct
22 Correct 492 ms 37064 KB Output is correct
23 Correct 573 ms 37672 KB Output is correct
24 Correct 554 ms 37356 KB Output is correct
25 Correct 383 ms 36732 KB Output is correct
26 Correct 520 ms 38012 KB Output is correct
27 Correct 341 ms 35884 KB Output is correct
28 Correct 365 ms 35896 KB Output is correct
29 Correct 313 ms 35952 KB Output is correct
30 Incorrect 464 ms 36088 KB Output is incorrect: {s, t} is wrong.
31 Halted 0 ms 0 KB -