제출 #1015481

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1015481		mansur	Highway Tolls (IOI18_highway)	C++17	18 / 100	108 ms	145300 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], s[N], h;
 
void dfs(int u, int id, int dt) {
	if (dt > N) exit(0);
	s[dt].push_back({u, id});
	for (auto [to, i]: g[u]) {
		if (i == id) continue;
		dfs(to, i, dt + 1);
	}
}
 
void dsf(int u, int id, int dt) {
	if (!dt) {
		h.push_back({id, u});
		return;
	}
	for (auto [to, i]: g[u]) {
 		if (i == id) continue;
		dsf(to, i, dt - 1);
	}
}
 
void find_pair(int n, vector<int> u, vector<int> v, int a, int b) {
	if (sz(u) == 4 && n == 4) {
		answer(1, 3);
		return;
	}
	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];
	dfs(y, l, 0);
	l = 0, r = n;
	while (l <= r) {
		int m = (l + r) / 2;
		for (int i = m; i <= n; i++) {
			for (auto [vt, id]: s[i]) {
				w[id] = 1;
			}
		}
		if (ask(w) == dt) r = m - 1;
		else l = m + 1;
		for (int i = m; i <= n; i++) {
			for (auto [vt, id]: s[i]) {
				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++) {
			w[s[z][i].s] = 1;
		}
		if (ask(w) == dt) l = m + 1;
		else r = m - 1;
		for (int i = 0; i <= m; i++) {
			w[s[z][i].s] = 0;
		}
	}
	x = s[z][l].f;
	dt /= a;
	dsf(x, -1, dt);
	l = 0, r = sz(h) - 1;
	while (l <= r) {
		int m = (l + r) / 2;
		for (int i = 0; i <= m; i++) w[h[i].f] = 1;
		if (ask(w) == dt * 1ll * a) l = m + 1;
		else r = m - 1;
		for (int i = 0; i <= m; i++) w[h[i].f] = 0; 
	}
	answer(x, h[l].s);
}
 

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