oj.uz

Submission #799450

# Submission time Handle Problem Language Result Execution time Memory
799450 2023-07-31T14:43:25 Z Sohsoh84 Highway Tolls (IOI18_highway) C++17
23 / 100
 610 ms 43668 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;
	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 27680 KB Output is correct
3 Correct 14 ms 27728 KB Output is correct
4 Correct 14 ms 27728 KB Output is correct
5 Correct 14 ms 27748 KB Output is correct
6 Correct 15 ms 27740 KB Output is correct
7 Correct 16 ms 27672 KB Output is correct
8 Correct 14 ms 27728 KB Output is correct
9 Correct 15 ms 27676 KB Output is correct
10 Correct 14 ms 27728 KB Output is correct
11 Correct 15 ms 27728 KB Output is correct
12 Correct 14 ms 27640 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 27728 KB Output is correct
2 Correct 67 ms 28752 KB Output is correct
3 Correct 548 ms 37296 KB Output is correct
4 Correct 491 ms 37008 KB Output is correct
5 Correct 519 ms 37244 KB Output is correct
6 Correct 516 ms 36984 KB Output is correct
7 Correct 527 ms 37260 KB Output is correct
8 Correct 515 ms 37200 KB Output is correct
9 Correct 516 ms 37272 KB Output is correct
10 Correct 489 ms 37268 KB Output is correct
11 Correct 513 ms 38704 KB Output is correct
12 Correct 507 ms 39532 KB Output is correct
13 Correct 497 ms 38552 KB Output is correct
14 Incorrect 520 ms 38984 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 96 ms 30944 KB Output is correct
3 Correct 56 ms 30340 KB Output is correct
4 Correct 327 ms 40388 KB Output is correct
5 Correct 337 ms 40436 KB Output is correct
6 Correct 382 ms 41820 KB Output is correct
7 Correct 135 ms 34856 KB Output is correct
8 Correct 362 ms 41096 KB Output is correct
9 Incorrect 482 ms 43668 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 28740 KB Output is correct
3 Correct 268 ms 34460 KB Output is correct
4 Correct 238 ms 35704 KB Output is correct
5 Correct 398 ms 36752 KB Output is correct
6 Correct 109 ms 34828 KB Output is correct
7 Correct 290 ms 36124 KB Output is correct
8 Correct 208 ms 35680 KB Output is correct
9 Incorrect 504 ms 37184 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 66 ms 28816 KB Output is correct
2 Correct 69 ms 28928 KB Output is correct
3 Correct 512 ms 37472 KB Output is correct
4 Correct 448 ms 37844 KB Output is correct
5 Correct 536 ms 39004 KB Output is correct
6 Correct 477 ms 38576 KB Output is correct
7 Correct 519 ms 38876 KB Output is correct
8 Correct 552 ms 38808 KB Output is correct
9 Correct 187 ms 34916 KB Output is correct
10 Correct 197 ms 35292 KB Output is correct
11 Correct 143 ms 35084 KB Output is correct
12 Correct 418 ms 38004 KB Output is correct
13 Correct 519 ms 38856 KB Output is correct
14 Correct 544 ms 38624 KB Output is correct
15 Correct 531 ms 38772 KB Output is correct
16 Correct 309 ms 36964 KB Output is correct
17 Correct 454 ms 37740 KB Output is correct
18 Correct 390 ms 37180 KB Output is correct
19 Correct 456 ms 37748 KB Output is correct
20 Correct 317 ms 36880 KB Output is correct
21 Correct 537 ms 39064 KB Output is correct

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 28832 KB Output is correct
2 Correct 61 ms 28824 KB Output is correct
3 Correct 448 ms 37320 KB Output is correct
4 Correct 508 ms 37728 KB Output is correct
5 Correct 441 ms 37608 KB Output is correct
6 Correct 555 ms 39332 KB Output is correct
7 Correct 454 ms 37424 KB Output is correct
8 Correct 518 ms 37788 KB Output is correct
9 Correct 505 ms 38028 KB Output is correct
10 Correct 571 ms 39360 KB Output is correct
11 Correct 525 ms 38876 KB Output is correct
12 Correct 610 ms 39080 KB Output is correct
13 Correct 180 ms 35332 KB Output is correct
14 Correct 252 ms 35820 KB Output is correct
15 Correct 245 ms 35756 KB Output is correct
16 Correct 226 ms 35684 KB Output is correct
17 Correct 163 ms 35020 KB Output is correct
18 Correct 223 ms 36008 KB Output is correct
19 Correct 414 ms 38048 KB Output is correct
20 Correct 484 ms 38352 KB Output is correct
21 Correct 557 ms 38908 KB Output is correct
22 Correct 524 ms 38388 KB Output is correct
23 Correct 541 ms 38972 KB Output is correct
24 Correct 543 ms 38764 KB Output is correct
25 Correct 378 ms 37980 KB Output is correct
26 Correct 576 ms 39244 KB Output is correct
27 Correct 348 ms 36936 KB Output is correct
28 Correct 380 ms 36936 KB Output is correct
29 Correct 341 ms 37060 KB Output is correct
30 Incorrect 522 ms 37212 KB Output is incorrect: {s, t} is wrong.
31 Halted 0 ms 0 KB -