Submission #830882

#	Time	Username	Problem	Language	Result	Execution time	Memory
830882		tranxuanbach	Highway Tolls (IOI18_highway)	C++17	69 / 100	136 ms	14752 KiB

highway

#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 / 5
• Subtask 2: 7 / 7
• Subtask 3: 6 / 6
• Subtask 4: 33 / 33
• Subtask 5: 18 / 18
• Subtask 6: 0 / 31