Submission #104711

#	Time	Username	Problem	Language	Result	Execution time	Memory
104711		turbat	Highway Tolls (IOI18_highway)	C++14	51 / 100	260 ms	15152 KiB

highway

#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
using pii = pair <int, int>;
using vi = vector <int>;
#define N 200005
#define pb push_back
#define F first
#define S second
#define mp make_pair
#define ll long long
int deep[N], cnt, flat[N], len,  curdeep;
vector <pii> edg[N];
pii parent[N];
bool vis[N];
void dfs(int u){
	vis[u] = 1;
	flat[cnt++] = u;
	for (pii v : edg[u])
		if (!vis[v.F]){
			dfs(v.F);
			parent[v.F] = mp(u, v.S);			
		}
}
void find_pair(int n, vector<int> U, vector<int> V, int A, int B) {
  	int M = U.size();
 	vi v(M);
 	ll maxdist, dist;
 	for (int i = 0;i < M;i++) v[i] = 1;
 	maxdist = ask(v);
 	for (int i = 0;i < M;i++) v[i] = 0;
 	for (int i = 0;i < M;i++){
 		edg[U[i]].pb(mp(V[i], i));
 		edg[V[i]].pb(mp(U[i], i));
 	}
 	dfs(0);
 	int l = 1, r = n - 1, mid;
 	while (l != r){
 		mid = (l + r) / 2;
 		for (int i = l;i <= mid;i++)
 			v[parent[flat[i]].S] = 1;
 		dist = ask(v);
 		if (dist < maxdist) l = mid + 1;
 		else {
 			r = mid;
	 		for (int i = l;i <= mid;i++)
	 			v[parent[flat[i]].S] = 0;
 		}
 	}
 	for (int i = 0;i < M;i++) v[i] = 0;
 	int s = flat[l];
 	cnt = 0;
 	memset(vis, 0, sizeof vis);
 	dfs(s);
 	l = 1, r = n - 1;
 	while (l != r){
 		mid = (l + r) / 2;
 		for (int i = l;i <= mid;i++)
 			v[parent[flat[i]].S] = 1;
 		dist = ask(v);
 		if (dist < maxdist) l = mid + 1;
 		else {
 			r = mid;
	 		for (int i = l;i <= mid;i++)
	 			v[parent[flat[i]].S] = 0;
 		}
 	}
 	int t = flat[l];
 	answer(s, t);
}

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