제출 #298418

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
298418		keko37	통행료 (IOI18_highway)	C++14	0 / 100	257 ms	19396 KiB

highway

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

using namespace std;

typedef long long llint;
typedef pair <int, int> pi;
typedef vector <int> vi;

const int MAXN = 90005;
const int MAXM = 150005;

llint n, m, a, b, L, cnt;
int ea[MAXM], eb[MAXM], ok[MAXM];
int bio[MAXN], par[MAXN], pe[MAXN];
vector <pi> v[MAXN], nodes;
vector <int> nula, jen, edges, ch[MAXN];
queue <int> q;

llint pitaj (vi e) {
	vi q(m);
	for (auto i : e) q[i] = 1;
	return ask(q);
}

llint get_length () {
	vector <int> e;
	return pitaj(e);
}

int find_edge (vi curr) {
	int siz = curr.size();
	if (siz == 1) return curr[0];
	vi lo, hi;
	for (int i = 0; i < siz; i++) {
		if (2 * i < siz) lo.push_back(curr[i]); else hi.push_back(curr[i]);
	}
	edges.clear();
	for (auto i : jen) edges.push_back(i);
	for (auto i : lo) edges.push_back(i);
	if (pitaj(edges) == L) {
		for (auto i : lo) jen.push_back(i);
		return find_edge(hi);
	} else {
		for (auto i : hi) nula.push_back(i);
		return find_edge(lo);
	}
}

void bfs (int ra, int rb) {
	edges.clear();
	memset(bio, -1, sizeof bio);
	bio[ra] = bio[rb] = 0;
	par[ra] = par[rb] = -1;
	q.push(ra); q.push(rb);
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (auto pp : v[x]) {
			int sus = pp.first, ind = pp.second;
			if (bio[sus] == -1) {
				ch[x].push_back(sus);
				par[sus] = x;
				pe[sus] = ind;				
				bio[sus] = 1 + bio[x];
				q.push(sus);
			}
		}
	}
	for (int i = 0; i < n; i++) {
		if (par[i] != -1) ok[pe[i]] = 1;
	}
}

void dfs (int x, int rod) {
	cnt++;
	nodes.push_back({bio[x], x});
	for (auto sus : ch[x]) {
		dfs(sus, x);
	}
}

int solve_subtree (int root, int rod) {
	cnt = 0;
	dfs(root, rod);
	sort(nodes.begin(), nodes.end());
	int lo = 0, hi = cnt - 1;
	while (lo < hi) {
		int mid = (lo + hi + 1) / 2;
		edges.clear();
		for (int i = 0; i < m; i++) {
			if (!ok[i]) edges.push_back(i);
		}
		for (int i = mid; i < cnt; i++) {
			int node = nodes[i].second;
			edges.push_back(pe[node]);
		}
		if (pitaj(edges) > L) {
			lo = mid;
		} else {
			hi = mid - 1;
		}
	}
	return nodes[lo].second;
}

void find_pair (int N, vi U, vi V, int A, int B) {
	n = N; m = U.size(), a = A, b = B;
	for (int i = 0; i < m; i++) {
		ea[i] = U[i], eb[i] = V[i];
		v[U[i]].push_back({V[i], i});
		v[V[i]].push_back({U[i], i});
	}
	L = get_length();

	vi curr_edges;
	for (int i = 0; i < m; i++) curr_edges.push_back(i);
	int ind = find_edge(curr_edges);
	ok[ind] = 1;
	bfs(ea[ind], eb[ind]);
	int sola = solve_subtree(ea[ind], eb[ind]);
	int solb = solve_subtree(eb[ind], ea[ind]);
	answer(sola, solb);
}

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