제출 #74973

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
74973		khsoo01	통행료 (IOI18_highway)	C++11	90 / 100	530 ms	21484 KiB

highway

#include "highway.h"
#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int N = 90005, M = 1300005;
const ll inf = 1e18;

int n, m, a, b, p;
ll def, dis[N];
bool ban[N], v1[N], v2[N];

vector<int> adj[N], dij[N], drv[N], ord;
vector<pii> edg;

queue<int> q;

ll query () {
	vector<int> V;
	for(int i=0;i<m;i++) {
		V.push_back(ban[edg[i].X] || ban[edg[i].Y]);
	}
	return ask(V);
}

int getpiv () {
	int S = 0, E = (int)ord.size() - 1;
	while(S<E) {
		int Z = (S+E)/2;
		for(int i=0;i<=Z;i++) {
			ban[ord[i]] = true;
		}
		query() != def ? E = Z : S = Z+1;
		for(int i=0;i<=Z;i++) {
			ban[ord[i]] = false;
		}
	}
	return ord[S];
}

void dfs1 (int C) {
	if(C == p || v1[C]) return;
	v1[C] = true;
	for(auto &T : drv[C]) {
		dfs1(T);
	}
}

void dfs2 (int C) {
	if(v2[C]) return;
	v2[C] = true;
	for(auto &T : dij[C]) {
		dfs2(T);
	}
}

void find_pair(int _N, vector<int> _U, vector<int> _V, int _A, int _B) {
	n = _N;
	m = (int)_U.size();
	a = _A;
	b = _B;
	for(int i=0;i<m;i++) {
		edg.push_back({_U[i]+1, _V[i]+1});
		adj[_U[i]+1].push_back(_V[i]+1);
		adj[_V[i]+1].push_back(_U[i]+1);
	}
	for(int i=0;i<5;i++) query();
	def = query();
	for(int i=1;i<=n;i++) {
		ord.push_back(i);
	}
	p = getpiv();
	ord.clear();
	for(int i=1;i<p;i++) {
		ban[i] = true;
	}
	for(int i=1;i<=n;i++) {
		dis[i] = inf;
	}
	dis[p] = 0;
	q.push(p);
	while(!q.empty()) {
		int C = q.front();
		q.pop();
		ord.push_back(C);
		for(auto &T : adj[C]) {
			if(T < p) continue;
			if(dis[T] == inf) {
				dis[T] = dis[C] + 1;
				q.push(T);
			}
			if(dis[T] == dis[C] - 1) {
				dij[T].push_back(C);
				drv[C].push_back(T);
			}
		}
	}
	reverse(ord.begin(), ord.end());
	int PA = getpiv();
	ord.clear();
	dfs1(PA);
	for(int i=p;i<=n;i++) {
		if(v1[i]) dfs2(i);
	}
	for(int i=p;i<=n;i++) {
		if(!v2[i] && dis[i] + dis[PA] == def / a) ord.push_back(i);
	}
	int PB = getpiv();
	ord.clear();
	answer(PA-1, PB-1);
}

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