Submission #292709

#	Time	Username	Problem	Language	Result	Execution time	Memory
292709		theStaticMind	Highway Tolls (IOI18_highway)	C++14	5 / 100	672 ms	262148 KiB

highway

#include<bits/stdc++.h>
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define modulo 1000000007
#define mod 998244353
using namespace std;

#include "highway.h"

vector<int>adj[200000];
vector<int> d;
vector<int> D(200000, 0);
map<ii, int> edge;
vector<int> ptr;

void dfs(int x, int pre, int dep){
	for(auto y : adj[x]){
		if(y == pre) continue;
		d[edge[{x, y}]] = dep;
		D[y] = D[x] + 1;
		dfs(y, x, dep + 1);
	}
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	int M = U.size();
	int mn = ask(vector<int>(M, 0));

	for(int i = 0; i < M; i++){
		edge[{U[i], V[i]}] = i;
		edge[{V[i], U[i]}] = i;
		ptr.pb(i);
		adj[U[i]].pb(V[i]);
		adj[V[i]].pb(U[i]);
		d.pb(0);
	}

	auto lower = [&](int x){
		D[x] = 0;
		dfs(x, -1, 0);
		sort(all(ptr), [&](int x, int y){return d[x] > d[y];});
		int l = 0, r = M - 1;
		int ret = M - 1;
		while(l <= r){
			int m = (l + r) / 2;
			vector<int> Q(M, 0);
			for(int i = 0; i <= m; i++) Q[ptr[i]] = 1;
			if(ask(Q) != mn){
				ret = m;
				r = m - 1;
			}
			else l = m + 1;
		}
		return ptr[ret];
	};

	int b = 0, e = 0;
	b = lower(0);
	int bb = U[b];
	if(D[V[b]] > D[U[b]]) bb = V[b];

	e = lower(bb);
	int ee = U[e];
	if(D[V[e]] > D[U[e]]) ee = V[e];

	if(bb > ee) swap(bb, ee);

	answer(bb, ee);
}

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