oj.uz

Submission #830881

# Submission time Handle Problem Language Result Execution time Memory
830881 2023-08-19T12:22:31 Z tranxuanbach Highway Tolls (IOI18_highway) C++17
18 / 100
 176 ms 9992 KB 
#include "highway.h"

#include <bits/stdc++.h>
using namespace std;

#define isz(a) ((signed)a.size())

using ll = long long;

struct edge_t{
	int u, v;
};

const int N = 90'000 + 5, M = 130'000 + 5, LN = 17;

int n, m;
int a, b;
vector <edge_t> edge;
vector <int> adj[N];

vector <int> vquery;

namespace subtask1234{
	bool check(){
		return m == n - 1;
	}

	int length_path;

	int pv[N];
	int pe[N];
	int ctrtour, tour[N];

	void dfs_tour(int u){
		tour[ctrtour] = u;
		ctrtour++;
		for (auto i: adj[u]){
			if (i == pe[u]){
				continue;
			}
			auto v = u ^ edge[i].u ^ edge[i].v;
			pv[v] = u;
			pe[v] = i;
			dfs_tour(v);
		}
	}

	int solve_fixed(int s){
		pv[s] = -1;
		pe[s] = -1;
		ctrtour = 0;
		dfs_tour(s);

		int lo = 1, hi = n - 1;
		while (lo < hi){
			int mid = (lo + hi) >> 1;
			fill(vquery.begin(), vquery.end(), 0);
			for (int pos = 1; pos <= mid; pos++){
				vquery[pe[tour[pos]]] = 1;
			}
			if (ask(vquery) == (ll)length_path * b){
				hi = mid;
			}
			else{
				lo = mid + 1;
			}
		}
		return tour[lo];
	}

	int depth[N];

	void dfs_depth(int u){
		for (auto i: adj[u]){
			if (i == pe[u]){
				continue;
			}
			int v = u ^ edge[i].u ^ edge[i].v;
			pv[v] = u;
			pe[v] = i;
			depth[v] = depth[u] + 1;
			dfs_depth(v);
		}
	}

	int find_one(){
		int root = 1;
		pv[root] = -1;
		pe[root] = -1;
		depth[root] = 0;
		dfs_depth(root);

		int lo = 1, hi = *max_element(depth, depth + n);
		while (lo < hi){
			int mid = (lo + hi + 1) >> 1;
			fill(vquery.begin(), vquery.end(), 0);
			for (int u = 0; u < n; u++){
				if (depth[u] >= mid){
					vquery[pe[u]] = 1;
				}
			}
			if (ask(vquery) == (ll)length_path * a){
				hi = mid - 1;
			}
			else{
				lo = mid;
			}
		}
		vector <int> layer;
		for (int u = 0; u < n; u++){
			if (depth[u] == lo){
				layer.emplace_back(u);
			}
		}
		lo = 0; hi = isz(layer) - 1;
		while (lo < hi){
			int mid = (lo + hi) >> 1;
			fill(vquery.begin(), vquery.end(), 0);
			for (int i = 0; i <= mid; i++){
				vquery[pe[layer[i]]] = 1;
			}
			if (ask(vquery) == (ll)length_path * a){
				lo = mid + 1;
			}
			else{
				hi = mid;
			}
		}
		return layer[lo];
	}

	void solve(){
		fill(vquery.begin(), vquery.end(), 0);
		length_path = ask(vquery) / a;
		int s = find_one();
		int t = solve_fixed(s);
		answer(s, t);
	}
}

namespace subtask5{
	bool check(){
		return a == 1 and b == 2;
	}

	int odd_weight;
	int even_weight;
	int color[N];

	bool same_color(){
		for (int i = 0; i < m; i++){
			auto &[u, v] = edge[i];
			vquery[i] = (color[u] == color[v] ? even_weight : odd_weight);
		}
		return (ask(vquery) % 2 == 0 ? true : false);
	}

	bool same[LN];

	void solve(){
		odd_weight = (a % 2 != 0 ? 0 : 1);
		even_weight = 1 - odd_weight;

		for (int bit = 0; bit < LN; bit++){
			for (int u = 0; u < n; u++){
				color[u] = u >> bit & 1;
			}
			same[bit] = same_color();
		}
		int s = -1, t = -1;
		for (int bit = 0; bit < LN; bit++){
			if (same[bit]){
				continue;
			}
			vector <int> cpn;
			for (int u = 0; u < n; u++){
				if (u >> bit & 1){
					cpn.emplace_back(u);
				}
			}
			while (isz(cpn) != 1){
				vector <int> cpn1, cpn2;
				for (auto u: cpn){
					if (isz(cpn1) <= isz(cpn2)){
						cpn1.emplace_back(u);
					}
					else{
						cpn2.emplace_back(u);
					}
				}
				fill(color, color + n, 0);
				for (auto u: cpn1){
					color[u] = 1;
				}
				if (not same_color()){
					cpn = cpn1;
				}
				else{
					cpn = cpn2;
				}
			}
			s = cpn.back();
			break;
		}
		t = s;
		for (int bit = 0; bit < LN; bit++){
			if (not same[bit]){
				t ^= (1 << bit);
			}
		}
		answer(s, t);
	}
}

void find_pair(int _n, vector <int> _u, vector <int> _v, int _a, int _b){
	n = _n;
	m = isz(_u);
	edge.resize(m);
	for (int i = 0; i < m; i++){
		int u = _u[i], v = _v[i];
		edge[i] = edge_t{u, v};
		adj[u].emplace_back(i);
		adj[v].emplace_back(i);
	}
	a = _a;
	b = _b;
	vquery.resize(m);

	// if (subtask1234::check()){
	// 	subtask1234::solve();
	// 	return;
	// }
	if (subtask5::check()){
		subtask5::solve();
		return;
	}
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Incorrect 1 ms 2384 KB Output is incorrect: answered not exactly once.
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2384 KB Output is incorrect: answered not exactly once.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 2880 KB Output is incorrect: answered not exactly once.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2384 KB Output is correct
2 Incorrect 9 ms 3004 KB Output is incorrect: answered not exactly once.
3 Halted 0 ms 0 KB -

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3152 KB Output is correct
2 Correct 12 ms 3240 KB Output is correct
3 Correct 95 ms 8884 KB Output is correct
4 Correct 104 ms 9260 KB Output is correct
5 Correct 160 ms 9992 KB Output is correct
6 Correct 116 ms 9820 KB Output is correct
7 Correct 168 ms 9972 KB Output is correct
8 Correct 121 ms 9828 KB Output is correct
9 Correct 143 ms 7876 KB Output is correct
10 Correct 138 ms 8268 KB Output is correct
11 Correct 148 ms 8400 KB Output is correct
12 Correct 176 ms 9424 KB Output is correct
13 Correct 120 ms 9632 KB Output is correct
14 Correct 162 ms 9732 KB Output is correct
15 Correct 141 ms 9680 KB Output is correct
16 Correct 127 ms 8672 KB Output is correct
17 Correct 112 ms 8984 KB Output is correct
18 Correct 81 ms 8968 KB Output is correct
19 Correct 82 ms 9004 KB Output is correct
20 Correct 109 ms 9064 KB Output is correct
21 Correct 118 ms 9864 KB Output is correct

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 3024 KB Output is incorrect: answered not exactly once.
2 Halted 0 ms 0 KB -