oj.uz

Submission #799388

# Submission time Handle Problem Language Result Execution time Memory
799388 2023-07-31T13:41:36 Z Sohsoh84 Highway Tolls (IOI18_highway) C++17
12 / 100
 147 ms 37576 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;

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

void dfs(int v, int p) {
	dfs_order.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);
	}
}


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

	dfs(root, root);
	int l = 1, r = int(dfs_order.size()) - 1;

	while (l < r) {
		int mid = (l + r) >> 1;	
		if (getp(1, mid) == mn) r = mid;
		else l = mid + 1;
	}

	return dfs_order[l];

}

int dist[MAXN];

const double Z = 0.4;

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;
	memset(dist, 63, sizeof dist);
	q.push(v);
	dist[v] = 0;

	while (!q.empty()) {
		int v = q.front();
		q.pop();

		for (int ind : adj[v]) {
			int u = f(ind, v);
			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;

	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(0);
	int u = find(v);
	
	cerr << u << sep << v << endl;

	answer(u, v);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 27672 KB Output is correct
2 Correct 12 ms 27636 KB Output is correct
3 Correct 14 ms 27672 KB Output is correct
4 Correct 14 ms 27680 KB Output is correct
5 Correct 15 ms 27744 KB Output is correct
6 Correct 15 ms 27716 KB Output is correct
7 Correct 15 ms 27728 KB Output is correct
8 Correct 13 ms 27672 KB Output is correct
9 Correct 15 ms 27812 KB Output is correct
10 Correct 13 ms 27688 KB Output is correct
11 Correct 13 ms 27676 KB Output is correct
12 Correct 13 ms 27644 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 27736 KB Output is correct
2 Correct 25 ms 28588 KB Output is correct
3 Correct 127 ms 35064 KB Output is correct
4 Correct 125 ms 35008 KB Output is correct
5 Correct 147 ms 35064 KB Output is correct
6 Correct 116 ms 35088 KB Output is correct
7 Correct 132 ms 35068 KB Output is correct
8 Correct 121 ms 34996 KB Output is correct
9 Correct 120 ms 35072 KB Output is correct
10 Correct 145 ms 35072 KB Output is correct
11 Correct 130 ms 36620 KB Output is correct
12 Correct 133 ms 37576 KB Output is correct
13 Correct 126 ms 36796 KB Output is correct
14 Correct 129 ms 36860 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 28384 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 27744 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 28468 KB Output is correct
2 Correct 27 ms 28640 KB Output is correct
3 Incorrect 117 ms 35284 KB Output is incorrect: {s, t} is wrong.
4 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 28628 KB Output is correct
2 Correct 27 ms 28644 KB Output is correct
3 Incorrect 122 ms 34376 KB Output is incorrect: {s, t} is wrong.
4 Halted 0 ms 0 KB -