oj.uz

Submission #108104

# Submission time Handle Problem Language Result Execution time Memory
108104 2019-04-27T10:35:48 Z Noam527 Highway Tolls (IOI18_highway) C++17
51 / 100
 321 ms 11684 KB 
#include <bits/stdc++.h>
#define CHECK cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll inf = 1e18;
const int OO = 0;
const int OOO = 1;
using namespace std;

void answer(int s, int t);

ll ask(const vector<int> &w);

struct edge {
	int to, i;
	edge() {}
	edge(int tt, int ii) {
		to = tt;
		i = ii;
	}
};

vector<int> w;
vector<int> ord;
vector<int> special;

int n, m;
ll d;
vector<vector<edge>> g;
vector<int> vis, dep;

int crit;

ll f(int x) {
	for (int i = 0; i < x; i++) w[ord[i]] = 0;
	for (int i = x; i < ord.size(); i++) w[ord[i]] = 1;
	return ask(w);
}

void bfs(int v) {
	ord.clear();
	vis.resize(n, 0);
	dep.resize(n, 0);
	vis[v] = 1;
	queue<int> q;
	q.push(v);
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (const auto &i : g[x])
			if (!vis[i.to]) {
				dep[i.to] = dep[x] + 1;
				ord.push_back(i.i);
				vis[i.to] = 1;
				q.push(i.to);
			}
	}
}
void dfs(int v) {
	vis[v] = 1;
	for (const auto &i : g[v])
		if (!vis[i.to] && w[i.i] == 0) {
			special[i.i] = 1;
			dfs(i.to);
		}
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	if (N == 2) {
		answer(0, 1);
		return;
	}
	n = N;
	g.resize(n);
	m = U.size();
	w.resize(m);
	for (int i = 0; i < m; i++) {
		g[U[i]].push_back(edge(V[i], i));
		g[V[i]].push_back(edge(U[i], i));
	}
	for (auto &i : w) i = 0;
	d = ask(w);
	if (OO) cout << "d = " << d << '\n';
	int lo, hi, mid;

	// 1: find edge on shortest path
	ord.resize(m);
	for (int i = 0; i < m; i++) ord[i] = i;
	lo = 0, hi = m;
	while (lo < hi) {
		mid = (lo + hi + 1) / 2;
		if (f(mid) == d) hi = mid - 1;
		else lo = mid;
	}
	crit = lo;
	if (OO) cout << "critical edge index " << crit << ", (" << U[crit] << ", " << V[crit] << ")\n";
	// 2: root at 1 end of the edge, and bsearch in the subtree of the other for S/T
	for (auto &i : w) i = 1;
	bfs(U[crit]);
	for (auto &i : ord) w[i] = 0;

	// determine all edges in the subtree of the other end
	for (auto &i : vis) i = 0;
	vis[U[crit]] = 1;
	special.resize(m, 0);
	special[crit] = 1;
	dfs(V[crit]);
	vector<int> ord1, ord2;
	for (const auto &i : ord)
		if (special[i])
			ord1.push_back(i);
		else
			ord2.push_back(i);

	if (OO) {
		cout << "rooted at " << U[crit] << '\n';
		cout << "bfs: ";
		for (const auto &i : ord) cout << i << " "; cout << '\n';
		cout << "ord1: ";
		for (const auto &i : ord1) cout << i << " "; cout << '\n';
		cout << "ord2: ";
		for (const auto &i : ord2) cout << i << " "; cout << '\n';
		cout << "dep: ";
		for (const auto &i : dep) cout << i << " "; cout << '\n';
	}

	// bsearch in the subtree
	ord = ord1;
	lo = 0, hi = (int)ord.size();
	while (lo < hi) {
		mid = (lo + hi + 1) / 2;
		if (f(mid) == d) hi = mid - 1;
		else lo = mid;
	}
	int S, T;
	if (OO) {
		cout << "first bsearch yields edge " << ord[lo] << '\n';
	}
	if (dep[U[ord[lo]]] > dep[V[ord[lo]]]) S = U[ord[lo]];
	else S = V[ord[lo]];
	if (OO) cout << "resulting in S = " << S << '\n';

	if ((ll)A * dep[S] == d) {
		T = U[crit];
		answer(S, T);
		return;
	}

	// bsearch on everything else
	for (auto &i : ord1) w[i] = 0;
	ord = ord2;
	lo = 0, hi = (int)ord.size();
	while (lo < hi) {
		mid = (lo + hi + 1) / 2;
		if (f(mid) == d) hi = mid - 1;
		else lo = mid;
	}
	if (OO) {
		cout << "second bsearch yields edge " << ord[lo] << '\n';
	}
	if (dep[U[ord[lo]]] > dep[V[ord[lo]]]) T = U[ord[lo]];
	else T = V[ord[lo]];
	if (OO) cout << "resulting in T = " << T << '\n';

	answer(S, T);
}

Compilation message

highway.cpp: In function 'll f(int)':
highway.cpp:38:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = x; i < ord.size(); i++) w[ord[i]] = 1;
                  ~~^~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:120:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (const auto &i : ord) cout << i << " "; cout << '\n';
   ^~~
highway.cpp:120:47: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for (const auto &i : ord) cout << i << " "; cout << '\n';
                                               ^~~~
highway.cpp:122:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (const auto &i : ord1) cout << i << " "; cout << '\n';
   ^~~
highway.cpp:122:48: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for (const auto &i : ord1) cout << i << " "; cout << '\n';
                                                ^~~~
highway.cpp:124:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (const auto &i : ord2) cout << i << " "; cout << '\n';
   ^~~
highway.cpp:124:48: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for (const auto &i : ord2) cout << i << " "; cout << '\n';
                                                ^~~~
highway.cpp:126:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (const auto &i : dep) cout << i << " "; cout << '\n';
   ^~~
highway.cpp:126:47: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for (const auto &i : dep) cout << i << " "; cout << '\n';
                                               ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 320 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 328 KB Output is correct
5 Correct 2 ms 296 KB Output is correct
6 Correct 2 ms 328 KB Output is correct
7 Correct 2 ms 396 KB Output is correct
8 Correct 2 ms 324 KB Output is correct
9 Correct 2 ms 380 KB Output is correct
10 Correct 2 ms 408 KB Output is correct
11 Correct 2 ms 328 KB Output is correct
12 Correct 2 ms 404 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 23 ms 1320 KB Output is correct
3 Correct 181 ms 9612 KB Output is correct
4 Correct 216 ms 9600 KB Output is correct
5 Correct 195 ms 9588 KB Output is correct
6 Correct 199 ms 9604 KB Output is correct
7 Correct 212 ms 9632 KB Output is correct
8 Correct 217 ms 9604 KB Output is correct
9 Correct 190 ms 9620 KB Output is correct
10 Correct 211 ms 9592 KB Output is correct
11 Correct 228 ms 9620 KB Output is correct
12 Correct 214 ms 10068 KB Output is correct
13 Correct 204 ms 9196 KB Output is correct
14 Correct 184 ms 9168 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1528 KB Output is correct
2 Correct 38 ms 2668 KB Output is correct
3 Correct 49 ms 3404 KB Output is correct
4 Correct 138 ms 10232 KB Output is correct
5 Correct 158 ms 10852 KB Output is correct
6 Correct 174 ms 9548 KB Output is correct
7 Correct 160 ms 9184 KB Output is correct
8 Correct 168 ms 9848 KB Output is correct
9 Correct 171 ms 9748 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 480 KB Output is correct
2 Correct 28 ms 1288 KB Output is correct
3 Correct 157 ms 7676 KB Output is correct
4 Correct 190 ms 9636 KB Output is correct
5 Correct 190 ms 9572 KB Output is correct
6 Correct 193 ms 9584 KB Output is correct
7 Correct 187 ms 9572 KB Output is correct
8 Correct 190 ms 9592 KB Output is correct
9 Correct 192 ms 9464 KB Output is correct
10 Correct 192 ms 9600 KB Output is correct
11 Correct 225 ms 9616 KB Output is correct
12 Correct 212 ms 9284 KB Output is correct
13 Correct 204 ms 9368 KB Output is correct
14 Correct 229 ms 9752 KB Output is correct
15 Correct 136 ms 9596 KB Output is correct
16 Correct 209 ms 9572 KB Output is correct
17 Correct 225 ms 9692 KB Output is correct
18 Correct 196 ms 9920 KB Output is correct
19 Correct 200 ms 9580 KB Output is correct
20 Correct 205 ms 10176 KB Output is correct
21 Correct 172 ms 10020 KB Output is correct
22 Correct 137 ms 10144 KB Output is correct
23 Correct 180 ms 9868 KB Output is correct
24 Correct 192 ms 9836 KB Output is correct
25 Correct 160 ms 9248 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1464 KB Output is correct
2 Correct 46 ms 1400 KB Output is correct
3 Correct 250 ms 10020 KB Output is correct
4 Correct 238 ms 10588 KB Output is correct
5 Correct 239 ms 11520 KB Output is correct
6 Correct 280 ms 11596 KB Output is correct
7 Correct 292 ms 11584 KB Output is correct
8 Correct 321 ms 11684 KB Output is correct
9 Incorrect 238 ms 8032 KB Output is incorrect: {s, t} is wrong.
10 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1420 KB Output is correct
2 Correct 24 ms 1392 KB Output is correct
3 Correct 221 ms 10028 KB Output is correct
4 Correct 250 ms 10192 KB Output is correct
5 Correct 255 ms 10564 KB Output is correct
6 Correct 293 ms 11608 KB Output is correct
7 Correct 231 ms 10060 KB Output is correct
8 Correct 252 ms 10348 KB Output is correct
9 Correct 251 ms 10584 KB Output is correct
10 Correct 276 ms 11592 KB Output is correct
11 Correct 316 ms 11604 KB Output is correct
12 Correct 286 ms 11640 KB Output is correct
13 Correct 252 ms 9080 KB Output is correct
14 Incorrect 245 ms 8368 KB Output is incorrect: {s, t} is wrong.
15 Halted 0 ms 0 KB -