제출 #830823

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
830823		tranxuanbach	통행료 (IOI18_highway)	C++17	51 / 100	149 ms	14768 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;

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);
	}
}

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;
	}
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 6 / 6
• Subtask 4: 33 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31