oj.uz

Submission #290588

# Submission time Handle Problem Language Result Execution time Memory
290588 2020-09-04T05:45:28 Z ChrisT Highway Tolls (IOI18_highway) C++17
51 / 100
 673 ms 29416 KB 
#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
const int MN = 9e4 + 5;
vector<pair<int,int>> adj[MN];
vector<pair<int,int>> atDep[MN];
pair<int,int> par[MN]; vector<int> w;
int depth[MN], mxDep;
void dfs (int cur, int p = -1) {
	if (~p) atDep[depth[cur]].push_back({cur,par[cur].second});
	mxDep = max(mxDep,depth[cur]);
	for (auto [i,j] : adj[cur]) if (i != p) {
		par[i] = {cur,j}; depth[i] = depth[cur] + 1;
		dfs(i,cur);
	}
}
void find_pair (int n, vector<int> u, vector<int> v, int a, int b) {
	assert((int)u.size() == n - 1);
	for (int i = 0; i + 1 < n; i++) {
		adj[++u[i]].emplace_back(++v[i],i);
		adj[v[i]].emplace_back(u[i],i);
	}
	w.resize(n-1);
	long long smallDist = ask(w);
	dfs(1);
	auto find = [&] (set<int> banned) {
		int low = 1, high = mxDep, mid, ans = -1;
		while (low <= high) {
			mid = (low + high) / 2;
			for (int i = mid; i <= mxDep; i++) for (auto p : atDep[i]) if (!banned.count(p.second)) w[p.second] = 1;
			if (ask(w) != smallDist) low = (ans = mid) + 1;
			else high = mid - 1;
			for (int i = mid; i <= mxDep; i++) for (auto p : atDep[i]) if (!banned.count(p.second))w[p.second] = 0;
		}
		if (!~ans) return -1;
		function<int(int,int)> get = [&] (int l, int r) {
			if (l == r) return atDep[ans][l].first;
			int mid = (l + r) / 2;
			for (int i = l; i <= mid; i++) if (!banned.count(atDep[ans][i].second)) w[atDep[ans][i].second] = 1;
			long long got = ask(w);
			for (int i = l; i <= mid; i++) if (!banned.count(atDep[ans][i].second)) w[atDep[ans][i].second] = 0;
			if (got != smallDist) return get(l,mid);
			return get(mid+1,r);
		};
		return get(0,(int)atDep[ans].size() - 1);
	};
	int s = find({});
	set<int> ban; int cur = s;
	while (cur != 1) {
		ban.insert(par[cur].second);
		cur = par[cur].first;
	}
	int t = find(ban);
	if (!~t) { //answer is on root-->s path
		vector<pair<int,int>> go;
		cur = s;
		while (cur != 1) {
			go.push_back(par[cur]);
			cur = par[cur].first;
		}
		int low = 0, high = (int)go.size() - 1,mid,ans=-1;
		while (low <= high) {
			mid = (low + high) / 2;
			w[go[mid].second] = 1;
			if (ask(w) != smallDist) low = (ans = mid) + 1;
			else high = mid - 1;
			w[go[mid].second] = 0;
		}
		assert(~ans);
		t = go[ans].first;
	}
	answer(--s,--t);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4608 KB Output is correct
2 Correct 3 ms 4608 KB Output is correct
3 Correct 3 ms 4608 KB Output is correct
4 Correct 4 ms 4608 KB Output is correct
5 Correct 3 ms 4608 KB Output is correct
6 Correct 3 ms 4608 KB Output is correct
7 Correct 3 ms 4608 KB Output is correct
8 Correct 3 ms 4608 KB Output is correct
9 Correct 3 ms 4608 KB Output is correct
10 Correct 3 ms 4608 KB Output is correct
11 Correct 3 ms 4608 KB Output is correct
12 Correct 3 ms 4608 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4608 KB Output is correct
2 Correct 16 ms 5376 KB Output is correct
3 Correct 161 ms 12036 KB Output is correct
4 Correct 160 ms 11912 KB Output is correct
5 Correct 155 ms 11944 KB Output is correct
6 Correct 155 ms 11828 KB Output is correct
7 Correct 159 ms 11896 KB Output is correct
8 Correct 160 ms 11976 KB Output is correct
9 Correct 154 ms 11948 KB Output is correct
10 Correct 170 ms 11948 KB Output is correct
11 Correct 420 ms 13952 KB Output is correct
12 Correct 480 ms 15668 KB Output is correct
13 Correct 472 ms 14864 KB Output is correct
14 Correct 454 ms 14008 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 6528 KB Output is correct
2 Correct 51 ms 8948 KB Output is correct
3 Correct 98 ms 12664 KB Output is correct
4 Correct 288 ms 26336 KB Output is correct
5 Correct 242 ms 24668 KB Output is correct
6 Correct 325 ms 28800 KB Output is correct
7 Correct 351 ms 29416 KB Output is correct
8 Correct 293 ms 27068 KB Output is correct
9 Correct 310 ms 27956 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4608 KB Output is correct
2 Correct 18 ms 5376 KB Output is correct
3 Correct 118 ms 10200 KB Output is correct
4 Correct 168 ms 11724 KB Output is correct
5 Correct 168 ms 11840 KB Output is correct
6 Correct 153 ms 11856 KB Output is correct
7 Correct 160 ms 12000 KB Output is correct
8 Correct 157 ms 11844 KB Output is correct
9 Correct 158 ms 11804 KB Output is correct
10 Correct 151 ms 11864 KB Output is correct
11 Correct 362 ms 13632 KB Output is correct
12 Correct 512 ms 16764 KB Output is correct
13 Correct 498 ms 15536 KB Output is correct
14 Correct 547 ms 16748 KB Output is correct
15 Correct 159 ms 11908 KB Output is correct
16 Correct 144 ms 11836 KB Output is correct
17 Correct 486 ms 16180 KB Output is correct
18 Correct 327 ms 14400 KB Output is correct
19 Correct 160 ms 11800 KB Output is correct
20 Correct 611 ms 18664 KB Output is correct
21 Correct 128 ms 12400 KB Output is correct
22 Correct 125 ms 12396 KB Output is correct
23 Correct 156 ms 12292 KB Output is correct
24 Correct 236 ms 13712 KB Output is correct
25 Correct 673 ms 27076 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 20 ms 9336 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 9344 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -