Submission #412248

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
412248	2021-05-26T15:59:42 Z	Mlxa	Highway Tolls (IOI18_highway)	C++14	5 / 100	252 ms	262148 KB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
#define mp make_pair
#define mt make_tuple
#define x first
#define y second

namespace my {
const int N = 1e6 + 10;
struct edge {
	int u, i;
	edge(int x, int y) : u(x), i(y) {}
	operator int() {
		return u;
	}
};
int bs(vector<int> p) {
	auto check = [&](int n) -> ll {
		assert(0 <= n && n <= (int)p.size());
		vector<int> w(p.size(), 0);
		for (int i = 0; i < n; ++i) {
			w[p[i]] = 1;
		}
		return ask(w);
	};
	int lef = -1, rig = (int)p.size();
	ll val = check(rig);
	while (rig - lef > 1) {
		int mid = (lef + rig) / 2;
		if (check(mid) == val) {
			rig = mid;
		} else {
			lef = mid;
		}
	}
	assert(rig - 1 < (int)p.size());
	assert(0 <= rig - 1);
	return p[rig - 1];
}
vector<edge> g[N];
vector<int> bin, bout;
void dfs(int v, int p) {
	for (auto u : g[v]) {
		if (u == p) {
			continue;
		}
		bin.push_back(u.i);
		dfs(u, v);
		bout.push_back(u.i);
	}
}
int d[N];
int p[N];
int e[N];

int far(int from, int x, int y) {
	queue<int> q;
	fill_n(d, N, -1);
	d[from] = 0;
	q.push(from);
	while (q.size()) {
		int v = q.front(); q.pop();
		for (auto u : g[v]) {
			if (d[u] == -1) {
				d[u] = d[v] + 1;
				q.push(u);
			}
		}
	}
	return d[x] > d[y] ? x : y;
}
bool check(int m, int a, int b, int x, int y) {
	queue<int> q;
	fill_n(d, N, -1);
	d[x] = 0;
	q.push(x);
	while (q.size()) {
		int v = q.front(); q.pop();
		for (auto u : g[v]) {
			if (d[u] == -1) {
				d[u] = d[v] + 1;
				p[u] = v;
				e[u] = u.i;
				q.push(u);
			}
		}
	}
	int v = y;
	vector<int> w(m, 0);
	ll d0 = ask(w);
	while (v != x) {
		int i = e[v];
		v = p[v];
		w[i] = 1;
	}
	ll d1 = ask(w);
	// cout << "check " << m << " " << a << " " << b << " " << x << " " << y << endl;
	// cout << "\t\t" << d0 << " " << d1 << " " << d[y] << endl;
	return d0 == a * d[y] && d1 == b * d[y];
}
}

void find_pair(int n, vector<int> u, vector<int> v, int a, int b) {
	using namespace my;
	(void)n;
	assert(a < b);
	int m = (int)u.size();
	for (int i = 0; i < m; ++i) {
		g[v[i]].emplace_back(u[i], i);
		g[u[i]].emplace_back(v[i], i);
	}
	dfs(0, 0);
	int x = bs(bin);
	int y = bs(bout);
	reverse(all(bout));
	int z = bs(bout);

	int fi = far(v[y], v[x], u[x]);
	int se = far(fi, v[y], u[y]);
	if (check(m, a, b, fi, se)) {
		answer(fi, se);
		return;
	}
	assert(false);
	fi = far(v[z], v[x], u[x]);
	se = far(fi, v[z], u[z]);
	assert(check(m, a, b, fi, se));
	answer(fi, se);
}

#ifdef LC
#include "grader.cpp"
#endif

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	27628 KB	Output is correct
2	Correct	26 ms	27584 KB	Output is correct
3	Correct	32 ms	27664 KB	Output is correct
4	Correct	19 ms	27692 KB	Output is correct
5	Correct	16 ms	27592 KB	Output is correct
6	Correct	16 ms	27592 KB	Output is correct
7	Correct	17 ms	27592 KB	Output is correct
8	Correct	17 ms	27592 KB	Output is correct
9	Correct	16 ms	27592 KB	Output is correct
10	Correct	17 ms	27628 KB	Output is correct
11	Correct	18 ms	27720 KB	Output is correct
12	Correct	20 ms	27632 KB	Output is correct

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	27772 KB	Output is correct
2	Correct	37 ms	28424 KB	Output is correct
3	Correct	239 ms	34348 KB	Output is correct
4	Correct	251 ms	34284 KB	Output is correct
5	Correct	233 ms	34272 KB	Output is correct
6	Correct	191 ms	34472 KB	Output is correct
7	Correct	252 ms	34320 KB	Output is correct
8	Correct	237 ms	34504 KB	Output is correct
9	Correct	239 ms	34208 KB	Output is correct
10	Correct	175 ms	34228 KB	Output is correct
11	Correct	239 ms	35160 KB	Output is correct
12	Correct	233 ms	35648 KB	Output is correct
13	Correct	187 ms	35236 KB	Output is correct
14	Runtime error	231 ms	70140 KB	Execution killed with signal 6

Subtask #3
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	32 ms	28972 KB	Output is correct
2	Correct	51 ms	30336 KB	Output is correct
3	Correct	56 ms	31684 KB	Output is correct
4	Correct	126 ms	39252 KB	Output is correct
5	Correct	137 ms	39280 KB	Output is correct
6	Correct	160 ms	39368 KB	Output is correct
7	Correct	173 ms	39292 KB	Output is correct
8	Correct	145 ms	39300 KB	Output is correct
9	Runtime error	240 ms	79520 KB	Execution killed with signal 6