Submission #412215

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
412215	2021-05-26T15:44:49 Z	Mlxa	Highway Tolls (IOI18_highway)	C++14	5 / 100	299 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(0 <= rig - 1 && rig - 1 < (int)p.size());
	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;
	assert(a < b);
	for (int i = 0; i < n - 1; ++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);
	for (int fi : {v[x], u[x]}) {
		for (int se : {v[y], u[y], v[z], u[z]}) {
			if (check((int)v.size(), a, b, fi, se)) {
				answer(fi, se);
				return;
			}
		}
	}
	assert(false);
}

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

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	27720 KB	Output is correct
2	Correct	32 ms	28456 KB	Output is correct
3	Correct	179 ms	34236 KB	Output is correct
4	Correct	221 ms	34244 KB	Output is correct
5	Incorrect	207 ms	34296 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #3
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	31 ms	28972 KB	Output is correct
2	Correct	52 ms	30528 KB	Output is correct
3	Correct	69 ms	31688 KB	Output is correct
4	Correct	183 ms	39264 KB	Output is correct
5	Correct	142 ms	39344 KB	Output is correct
6	Correct	184 ms	39336 KB	Output is correct
7	Correct	163 ms	39240 KB	Output is correct
8	Correct	144 ms	39300 KB	Output is correct
9	Runtime error	188 ms	79524 KB	Execution killed with signal 6