제출 #1015462

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1015462		mansur	통행료 (IOI18_highway)	C++17	11 / 100	121 ms	54896 KiB

highway

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

using namespace std;

#define rall(s) s.rbegin(), s.rend()
#define all(s) s.begin(), s.end()
#define sz(s) (int)s.size()
#define s second
#define f first

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int N = 1e6;

vector<pii> g[N];
vector<int> s[N], h;

int n;

void bfs(int u) {
	queue<int> q;
	vector<int> d(n, -1);
	d[u] = 0;
	q.push(u);
	while (sz(q)) {
		int x = q.front();
		s[d[x]].push_back(x);
		q.pop();
		for (auto [to, id]: g[x]) {
			if (d[to] == -1) {
				d[to] = d[x] + 1;
				q.push(to);
			}
		}
	}
}

void find_pair(int n1, vector<int> u, vector<int> v, int a, int b) {
	n = n1;
	for (int i = 0; i < sz(u); i++) {
		g[u[i]].push_back({v[i], i});
		g[v[i]].push_back({u[i], i});
	}
	vector<int> w(sz(u));
	ll dt = ask(w);	
	int l = 0, r = sz(u) - 1;
	while (l <= r) {
		int m = (l + r) / 2;
		for (int i = 0; i <= m; i++) w[i] = 1;
		if (ask(w) == dt) l = m + 1;
		else r = m - 1;
		for (int i = 0; i <= m; i++) w[i] = 0;
	}
	int x = u[l], y = v[l];
	bfs(y);
	l = 0, r = n;
	while (l <= r) {
		int m = (l + r) / 2;
		for (int i = m; i <= n; i++) {
			for (int vt: s[i]) {
				for (auto [to, id]: g[vt]) {
					w[id] = 1;
				}
			}
		}
		if (ask(w) == dt) r = m - 1;
		else l = m + 1;
		for (int i = m; i <= n; i++) {
			for (int vt: s[i]) {
				for (auto [to, id]: g[vt]) {
					w[id] = 0;
				}
			}
		}
	}
	int z = r;
	l = 0, r = sz(s[z]) - 1;
	while (l <= r) {
		int m = (l + r) / 2;
		for (int i = 0; i <= m; i++) {
			for (auto [to, id]: g[s[z][i]]) {
				w[id] = 1;	
		   	}
		}  	
		if (ask(w) == dt) l = m + 1;
		else r = m - 1;
		for (int i = 0; i <= m; i++) {
			for (auto [to, id]: g[s[z][i]]) {
				w[id] = 0;	
		   	}
		}
	}
	x = s[z][l];
	dt /= a;
	for (int i = 0; i <= n; i++) s[i].clear();
	bfs(x);
	h = s[dt];
	l = 0, r = sz(h) - 1;
	while (l <= r) {
		int m = (l + r) / 2;
		for (int i = 0; i <= m; i++) {
			for (auto [to, id]: g[h[i]]) w[id] = 1;
		}
		if (ask(w) == dt * 1ll * a) l = m + 1;
		else r = m - 1;
		for (int i = 0; i <= m; i++) {
			for (auto [to, id]: g[h[i]]) w[id] = 0;
		}
	}
	answer(x, h[l]);
}

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