Submission #830767

#	Time	Username	Problem	Language	Result	Execution time	Memory
830767		tranxuanbach	Highway Tolls (IOI18_highway)	C++17	12 / 100	124 ms	10784 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;
vector <edge_t> edge;
vector <int> adj[N];

vector <int> vquery;

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

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

	void dfs_tour(int u){
		tour[ctrtour] = u;
		ctrtour++;
		for (auto i: adj[u]){
			auto v = u ^ edge[i].u ^ edge[i].v;
			if (v == pv[u]){
				continue;
			}
			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);

		fill(vquery.begin(), vquery.end(), 1);
		ll length_path = ask(vquery);

		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) == length_path){
				hi = mid;
			}
			else{
				lo = mid + 1;
			}
		}
		return tour[lo];
	}

	void solve(){
		int s = 0;
		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);
	}
	vquery.resize(m);

	if (subtask12::check()){
		subtask12::solve();
		return;
	}
}

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