oj.uz

Submission #830882

# Submission time Handle Problem Language Result Execution time Memory
830882 2023-08-19T12:23:51 Z tranxuanbach Highway Tolls (IOI18_highway) C++17
69 / 100
 136 ms 14752 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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Correct 1 ms 2384 KB Output is correct
4 Correct 1 ms 2384 KB Output is correct
5 Correct 1 ms 2384 KB Output is correct
6 Correct 1 ms 2384 KB Output is correct
7 Correct 1 ms 2384 KB Output is correct
8 Correct 1 ms 2384 KB Output is correct
9 Correct 1 ms 2384 KB Output is correct
10 Correct 1 ms 2384 KB Output is correct
11 Correct 1 ms 2428 KB Output is correct
12 Correct 1 ms 2400 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2512 KB Output is correct
2 Correct 12 ms 3280 KB Output is correct
3 Correct 81 ms 9312 KB Output is correct
4 Correct 84 ms 9308 KB Output is correct
5 Correct 97 ms 9352 KB Output is correct
6 Correct 89 ms 9244 KB Output is correct
7 Correct 88 ms 9324 KB Output is correct
8 Correct 78 ms 9332 KB Output is correct
9 Correct 83 ms 9320 KB Output is correct
10 Correct 76 ms 9216 KB Output is correct
11 Correct 99 ms 10664 KB Output is correct
12 Correct 109 ms 11264 KB Output is correct
13 Correct 95 ms 10676 KB Output is correct
14 Correct 92 ms 10704 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3792 KB Output is correct
2 Correct 15 ms 5092 KB Output is correct
3 Correct 17 ms 6484 KB Output is correct
4 Correct 69 ms 14736 KB Output is correct
5 Correct 60 ms 14708 KB Output is correct
6 Correct 60 ms 14752 KB Output is correct
7 Correct 62 ms 14688 KB Output is correct
8 Correct 64 ms 14740 KB Output is correct
9 Correct 60 ms 14736 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2480 KB Output is correct
2 Correct 8 ms 3132 KB Output is correct
3 Correct 56 ms 7900 KB Output is correct
4 Correct 75 ms 9268 KB Output is correct
5 Correct 76 ms 9276 KB Output is correct
6 Correct 82 ms 9216 KB Output is correct
7 Correct 76 ms 9200 KB Output is correct
8 Correct 75 ms 9324 KB Output is correct
9 Correct 99 ms 9324 KB Output is correct
10 Correct 78 ms 9328 KB Output is correct
11 Correct 89 ms 10336 KB Output is correct
12 Correct 99 ms 10992 KB Output is correct
13 Correct 96 ms 10744 KB Output is correct
14 Correct 99 ms 11124 KB Output is correct
15 Correct 98 ms 9204 KB Output is correct
16 Correct 74 ms 9228 KB Output is correct
17 Correct 98 ms 10440 KB Output is correct
18 Correct 89 ms 10944 KB Output is correct
19 Correct 87 ms 9268 KB Output is correct
20 Correct 86 ms 11596 KB Output is correct
21 Correct 71 ms 9900 KB Output is correct
22 Correct 68 ms 9872 KB Output is correct
23 Correct 83 ms 9836 KB Output is correct
24 Correct 104 ms 10216 KB Output is correct
25 Correct 95 ms 14216 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3072 KB Output is correct
2 Correct 11 ms 3116 KB Output is correct
3 Correct 123 ms 8904 KB Output is correct
4 Correct 101 ms 9272 KB Output is correct
5 Correct 110 ms 9928 KB Output is correct
6 Correct 120 ms 9924 KB Output is correct
7 Correct 115 ms 9900 KB Output is correct
8 Correct 119 ms 9804 KB Output is correct
9 Correct 100 ms 7872 KB Output is correct
10 Correct 125 ms 8248 KB Output is correct
11 Correct 133 ms 8316 KB Output is correct
12 Correct 135 ms 9404 KB Output is correct
13 Correct 115 ms 9656 KB Output is correct
14 Correct 119 ms 9740 KB Output is correct
15 Correct 123 ms 9748 KB Output is correct
16 Correct 136 ms 8680 KB Output is correct
17 Correct 118 ms 8912 KB Output is correct
18 Correct 93 ms 8932 KB Output is correct
19 Correct 81 ms 8916 KB Output is correct
20 Correct 88 ms 9004 KB Output is correct
21 Correct 117 ms 9756 KB Output is correct

Subtask #6
0 / 31.0

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