Submission #765929

#	Time	Username	Problem	Language	Result	Execution time	Memory
765929		khshg	Highway Tolls (IOI18_highway)	C++14	6 / 100	216 ms	262144 KiB

highway

#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
 
using ll = long long;
using ld = long double;
using str = string;
 
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<ld, ld>;
#define mp make_pair
#define ff first
#define ss second
 
#define ar array
template<class T> using V = vector<T>;
using vi = V<int>;
using vb = V<bool>;
using vl = V<ll>;
using vd = V<ld>;
using vs = V<str>;
using vpi = V<pi>;
using vpl = V<pl>;
using vpd = V<pd>;
 
#define sz(x) (int)((x).size())
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) (x).rbegin(), (x).rend()
#define sor(x) sort(all(x))
#define rsz resize
#define ins insert
#define pb push_back
#define eb emplace_back
#define ft front()
#define bk back()
#define lb lower_bound
#define ub upper_bound
 
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for(int i = (b) - 1; i >= (a); --i)
#define R0F(i, a) ROF(i, 0, a)
#define rep(a) F0R(_, a)
#define trav(a, x) for(auto& a : x)
 
template<class T> bool ckmin(T& a, const T& b) { return (b < a ? a = b, 1 : 0); }
template<class T> bool ckmax(T& a, const T& b) { return (b > a ? a = b, 1 : 0); }
 
int N, M;
ll A, B;
V<vpi> adj;
vi dep, par;
 
void root(int S) {
	dep[S] = 0;
	trav(u, adj[S]) {
		if(u.ff == par[S]) continue;
		par[u.ff] = S;
		root(u.ff);
		ckmax(dep[S], dep[u.ff] + 1);
	}
}
 
void find_pair(int _N, vi x, vi y, int _A, int _B) {
	swap(N, _N);
	A = _A;
	B = _B;
	M = sz(x);
	adj.rsz(N);
	F0R(i, N) adj[i].clear();
	F0R(i, M) {
		adj[x[i]].eb(y[i], i);
		adj[y[i]].eb(x[i], i);
	}
 
	int dis = (int)(ask(vi(M, 0)) / A);
	int S;
	{// find starting node ideally in 30 calls
		int tl = 0, tr = N - 2;
		S = N - 1;
		while(tl <= tr) {
			int tm = (tl + tr) / 2;
			vi ASK(M, 0);
			F0R(i, tm + 1) ASK[i] = 1;
			if(ask(ASK) > dis * A) {
				S = tm;
				tr = tm - 1;
			} else {
				tl = tm + 1;
			}
		}
	}
	par.rsz(N); dep.rsz(N);
	par[S] = -1;
	root(S);
	int cur = S;
	F0R(i, dis) {
		assert(dep[cur] >= dis - i);
		vi oke;
		trav(u, adj[cur]) {
			if(u.ff == par[cur]) continue;
			if(dep[u.ff] >= dis - i - 1) oke.eb(u.ss);
		}
		int L = 0, R = sz(oke) - 1;
		while(L < R) {
			int MID = (L + R) / 2;
			vi ASK(M);
			FOR(j, L, MID + 1) ASK[oke[j]] = 1;
			if(ask(ASK) == A * dis) {
				L = MID + 1;
			} else {
				R = MID;
			}
		}
		cur = x[oke[L]] + y[oke[R]] - cur;
	}
	answer(S, cur);
}

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