Submission #159846

#	Time	Username	Problem	Language	Result	Execution time	Memory
159846		qkxwsm	Highway Tolls (IOI18_highway)	C++14	51 / 100	1409 ms	106376 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
	if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
	if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) ((x).size()))
#define ALL(x) (x).begin(), (x).end()
#define MAXN 90013

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

int N, T, U, V, M;
ll A, B, D;
vi edge[MAXN];
unordered_map<int, int> eid[MAXN];
int st[MAXN], rev[MAXN];
int parent[MAXN];
vi qry;

void dfs(int u, int p)
{
	st[u] = T; rev[T] = u;
	T++;
	for (int v : edge[u])
	{
		if (v == p) continue;
		parent[v] = u;
		dfs(v, u);
	}
}
void find_pair(int n, vi u, vi v, int a, int b)
{
	N = n; A = a; B = b; M = SZ(u); int lo, hi;
	FOR(i, 0, M)
	{
		edge[u[i]].PB(v[i]);
		edge[v[i]].PB(u[i]);
		eid[u[i]][v[i]] = i;
		eid[v[i]][u[i]] = i;
	}
	qry.resize(M); D = ask(qry);
	T = 0;
	dfs(0, N);
	//binary serach on euler tour.
	lo = 0; hi = N;
	while(hi > lo)
	{
		int mid = (hi + lo) >> 1;
		FOR(i, 0, M) qry[i] = 0;
		FOR(i, mid + 1, M)
		{
			int u = rev[i];
			qry[eid[u][parent[u]]] = 1;
		}
		if (ask(qry) == D) hi = mid;
		else lo = mid + 1;
	}
	U = rev[lo];
	T = 0;
	dfs(U, N);
	lo = 0; hi = N;
	while(hi > lo)
	{
		int mid = (hi + lo) >> 1;
		FOR(i, 0, M) qry[i] = 0;
		FOR(i, mid + 1, M)
		{
			int u = rev[i];
			qry[eid[u][parent[u]]] = 1;
		}
		if (ask(qry) == D) hi = mid;
		else lo = mid + 1;
	}
	V = rev[lo];
	// cerr << U << ',' << V << endl;
	answer(U, V);
	//binary search on euler tour twice.
}

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