oj.uz

Submission #799422

# Submission time Handle Problem Language Result Execution time Memory
799422 2023-07-31T14:04:49 Z Sohsoh84 Highway Tolls (IOI18_highway) C++17
0 / 100
 28 ms 29200 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));
}

int fucking_root, A, B;

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 / A * B) r = mid;
		else l = mid + 1;
	}

	return 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);
	
	cerr << u << sep << v << endl;

	answer(u, v);
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 7.0

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

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 29200 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 17 ms 27736 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 Incorrect 28 ms 28604 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

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