oj.uz

Submission #799466

# Submission time Handle Problem Language Result Execution time Memory
799466 2023-07-31T14:53:01 Z Sohsoh84 Highway Tolls (IOI18_highway) C++17
23 / 100
 557 ms 43564 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 = find(all(dfs_order), jahel[mid]) - dfs_order.begin();
			assert(tmid < dfs_order.size());
		}

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

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from highway.cpp:2:
highway.cpp: In function 'int find(int, int)':
highway.cpp:106:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |    assert(tmid < dfs_order.size());
      |           ~~~~~^~~~~~~~~~~~~~~~~~

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 27728 KB Output is correct
3 Correct 13 ms 27676 KB Output is correct
4 Correct 13 ms 27728 KB Output is correct
5 Correct 16 ms 27668 KB Output is correct
6 Correct 14 ms 27728 KB Output is correct
7 Correct 14 ms 27672 KB Output is correct
8 Correct 14 ms 27728 KB Output is correct
9 Correct 14 ms 27628 KB Output is correct
10 Correct 14 ms 27728 KB Output is correct
11 Correct 14 ms 27728 KB Output is correct
12 Correct 14 ms 27728 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 28800 KB Output is correct
3 Correct 506 ms 37340 KB Output is correct
4 Correct 519 ms 37084 KB Output is correct
5 Correct 506 ms 37148 KB Output is correct
6 Correct 475 ms 36980 KB Output is correct
7 Correct 477 ms 37268 KB Output is correct
8 Correct 471 ms 37260 KB Output is correct
9 Correct 489 ms 37300 KB Output is correct
10 Correct 523 ms 37268 KB Output is correct
11 Correct 511 ms 38688 KB Output is correct
12 Correct 502 ms 39456 KB Output is correct
13 Correct 504 ms 38624 KB Output is correct
14 Incorrect 482 ms 39168 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 55 ms 29412 KB Output is correct
2 Correct 121 ms 30976 KB Output is correct
3 Correct 56 ms 30356 KB Output is correct
4 Correct 309 ms 40604 KB Output is correct
5 Correct 325 ms 40468 KB Output is correct
6 Correct 393 ms 41908 KB Output is correct
7 Correct 128 ms 34708 KB Output is correct
8 Correct 378 ms 41164 KB Output is correct
9 Incorrect 513 ms 43564 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 27836 KB Output is correct
2 Correct 65 ms 28708 KB Output is correct
3 Correct 261 ms 34468 KB Output is correct
4 Correct 226 ms 35708 KB Output is correct
5 Correct 388 ms 36668 KB Output is correct
6 Correct 90 ms 34832 KB Output is correct
7 Correct 291 ms 36016 KB Output is correct
8 Correct 237 ms 35720 KB Output is correct
9 Incorrect 480 ms 37188 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 28728 KB Output is correct
2 Correct 71 ms 28828 KB Output is correct
3 Correct 520 ms 37464 KB Output is correct
4 Correct 444 ms 37748 KB Output is correct
5 Correct 557 ms 39112 KB Output is correct
6 Correct 500 ms 38584 KB Output is correct
7 Correct 535 ms 38876 KB Output is correct
8 Correct 501 ms 38808 KB Output is correct
9 Correct 180 ms 34932 KB Output is correct
10 Correct 179 ms 35296 KB Output is correct
11 Correct 171 ms 35064 KB Output is correct
12 Correct 443 ms 38004 KB Output is correct
13 Correct 461 ms 38760 KB Output is correct
14 Correct 508 ms 38832 KB Output is correct
15 Correct 503 ms 38756 KB Output is correct
16 Correct 299 ms 36952 KB Output is correct
17 Correct 457 ms 37564 KB Output is correct
18 Correct 399 ms 37188 KB Output is correct
19 Correct 533 ms 37776 KB Output is correct
20 Correct 281 ms 36880 KB Output is correct
21 Correct 552 ms 39048 KB Output is correct

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 28776 KB Output is correct
2 Correct 65 ms 28828 KB Output is correct
3 Correct 449 ms 37260 KB Output is correct
4 Correct 510 ms 37640 KB Output is correct
5 Correct 430 ms 37596 KB Output is correct
6 Correct 539 ms 39288 KB Output is correct
7 Correct 435 ms 37448 KB Output is correct
8 Correct 499 ms 37856 KB Output is correct
9 Correct 513 ms 38176 KB Output is correct
10 Correct 526 ms 39284 KB Output is correct
11 Correct 498 ms 38808 KB Output is correct
12 Correct 553 ms 39208 KB Output is correct
13 Correct 183 ms 35168 KB Output is correct
14 Correct 212 ms 35804 KB Output is correct
15 Correct 281 ms 35756 KB Output is correct
16 Correct 198 ms 35792 KB Output is correct
17 Correct 176 ms 35020 KB Output is correct
18 Correct 218 ms 36212 KB Output is correct
19 Correct 409 ms 38100 KB Output is correct
20 Correct 452 ms 38280 KB Output is correct
21 Correct 517 ms 38828 KB Output is correct
22 Correct 497 ms 38404 KB Output is correct
23 Correct 523 ms 39076 KB Output is correct
24 Correct 501 ms 38720 KB Output is correct
25 Correct 401 ms 38092 KB Output is correct
26 Correct 518 ms 39476 KB Output is correct
27 Correct 330 ms 36920 KB Output is correct
28 Correct 343 ms 36940 KB Output is correct
29 Correct 297 ms 37072 KB Output is correct
30 Incorrect 500 ms 37180 KB Output is incorrect: {s, t} is wrong.
31 Halted 0 ms 0 KB -