제출 #104710

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
104710		turbat	Highway Tolls (IOI18_highway)	C++14	0 / 100	26 ms	6136 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];
 	r = l;
 	l = 1;
 	while (l != r){
 		mid = (l + r + 1) / 2;
 		for (int i = mid;i <= r;i++)
 			v[parent[flat[i]].S] = 1;
 		if (dist < maxdist)	r = mid - 1;
 		else{
 			l = mid;
	 		for (int i = mid;i <= r;i++)
	 			v[parent[flat[i]].S] = 0;
 		}
 	}
 	int t = parent[flat[l]].F;
 	answer(s, t);
}

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