oj.uz

Submission #108107

# Submission time Handle Problem Language Result Execution time Memory
108107 2019-04-27T10:47:10 Z Noam527 Highway Tolls (IOI18_highway) C++17
100 / 100
 360 ms 12204 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);
	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 - 1;
	while (lo < hi) {
		mid = (lo + hi + 1) / 2;
		if (f(mid) == d) hi = mid - 1;
		else lo = mid;
	}
	crit = lo;
	// 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;
	// prioritize the critical edge
	for (auto &i : g[U[crit]])
		if (i.i == crit) {
			swap(i, g[U[crit]][0]);
		}
	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);

	// bsearch in the subtree
	ord = ord1;
	lo = 0, hi = (int)ord.size() - 1;
	while (lo < hi) {
		mid = (lo + hi + 1) / 2;
		if (f(mid) == d) hi = mid - 1;
		else lo = mid;
	}
	int S, T;
	if (dep[U[ord[lo]]] > dep[V[ord[lo]]]) S = U[ord[lo]];
	else S = V[ord[lo]];

	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() - 1;
	while (lo < hi) {
		mid = (lo + hi + 1) / 2;
		if (f(mid) == d) hi = mid - 1;
		else lo = mid;
	}
	if (dep[U[ord[lo]]] > dep[V[ord[lo]]]) T = U[ord[lo]];
	else T = V[ord[lo]];

	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;
                  ~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 396 KB Output is correct
2 Correct 18 ms 1400 KB Output is correct
3 Correct 231 ms 9600 KB Output is correct
4 Correct 200 ms 9592 KB Output is correct
5 Correct 211 ms 9576 KB Output is correct
6 Correct 206 ms 9588 KB Output is correct
7 Correct 204 ms 9580 KB Output is correct
8 Correct 210 ms 9608 KB Output is correct
9 Correct 209 ms 9640 KB Output is correct
10 Correct 202 ms 9596 KB Output is correct
11 Correct 217 ms 9572 KB Output is correct
12 Correct 216 ms 10080 KB Output is correct
13 Correct 191 ms 9164 KB Output is correct
14 Correct 204 ms 9172 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1536 KB Output is correct
2 Correct 42 ms 2624 KB Output is correct
3 Correct 60 ms 3408 KB Output is correct
4 Correct 172 ms 10224 KB Output is correct
5 Correct 154 ms 10800 KB Output is correct
6 Correct 176 ms 9552 KB Output is correct
7 Correct 167 ms 9236 KB Output is correct
8 Correct 146 ms 9896 KB Output is correct
9 Correct 166 ms 9724 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 34 ms 1280 KB Output is correct
3 Correct 164 ms 7672 KB Output is correct
4 Correct 227 ms 9600 KB Output is correct
5 Correct 173 ms 9616 KB Output is correct
6 Correct 199 ms 9588 KB Output is correct
7 Correct 177 ms 9596 KB Output is correct
8 Correct 195 ms 9588 KB Output is correct
9 Correct 218 ms 9524 KB Output is correct
10 Correct 191 ms 9592 KB Output is correct
11 Correct 225 ms 9560 KB Output is correct
12 Correct 206 ms 9344 KB Output is correct
13 Correct 225 ms 9360 KB Output is correct
14 Correct 241 ms 9804 KB Output is correct
15 Correct 193 ms 9580 KB Output is correct
16 Correct 189 ms 9576 KB Output is correct
17 Correct 241 ms 9720 KB Output is correct
18 Correct 231 ms 9880 KB Output is correct
19 Correct 195 ms 9600 KB Output is correct
20 Correct 239 ms 10060 KB Output is correct
21 Correct 186 ms 10040 KB Output is correct
22 Correct 182 ms 10012 KB Output is correct
23 Correct 189 ms 9776 KB Output is correct
24 Correct 183 ms 9832 KB Output is correct
25 Correct 214 ms 9252 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 1400 KB Output is correct
2 Correct 29 ms 1396 KB Output is correct
3 Correct 245 ms 10008 KB Output is correct
4 Correct 248 ms 10540 KB Output is correct
5 Correct 306 ms 11600 KB Output is correct
6 Correct 296 ms 11580 KB Output is correct
7 Correct 305 ms 11716 KB Output is correct
8 Correct 312 ms 11524 KB Output is correct
9 Correct 202 ms 7956 KB Output is correct
10 Correct 275 ms 8332 KB Output is correct
11 Correct 246 ms 9052 KB Output is correct
12 Correct 283 ms 10668 KB Output is correct
13 Correct 306 ms 11260 KB Output is correct
14 Correct 350 ms 11508 KB Output is correct
15 Correct 311 ms 11668 KB Output is correct
16 Correct 276 ms 9256 KB Output is correct
17 Correct 188 ms 9904 KB Output is correct
18 Correct 185 ms 10168 KB Output is correct
19 Correct 205 ms 9948 KB Output is correct
20 Correct 204 ms 9976 KB Output is correct
21 Correct 310 ms 12004 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1400 KB Output is correct
2 Correct 31 ms 1460 KB Output is correct
3 Correct 205 ms 10028 KB Output is correct
4 Correct 245 ms 10168 KB Output is correct
5 Correct 245 ms 10548 KB Output is correct
6 Correct 335 ms 11628 KB Output is correct
7 Correct 247 ms 10152 KB Output is correct
8 Correct 261 ms 10300 KB Output is correct
9 Correct 273 ms 10596 KB Output is correct
10 Correct 299 ms 11620 KB Output is correct
11 Correct 310 ms 11508 KB Output is correct
12 Correct 301 ms 11692 KB Output is correct
13 Correct 279 ms 9092 KB Output is correct
14 Correct 222 ms 8308 KB Output is correct
15 Correct 254 ms 9092 KB Output is correct
16 Correct 236 ms 8288 KB Output is correct
17 Correct 238 ms 9072 KB Output is correct
18 Correct 205 ms 8392 KB Output is correct
19 Correct 297 ms 10812 KB Output is correct
20 Correct 284 ms 11160 KB Output is correct
21 Correct 316 ms 11732 KB Output is correct
22 Correct 311 ms 11488 KB Output is correct
23 Correct 305 ms 11612 KB Output is correct
24 Correct 303 ms 11604 KB Output is correct
25 Correct 321 ms 11552 KB Output is correct
26 Correct 289 ms 11712 KB Output is correct
27 Correct 177 ms 9992 KB Output is correct
28 Correct 194 ms 9924 KB Output is correct
29 Correct 179 ms 10188 KB Output is correct
30 Correct 179 ms 10048 KB Output is correct
31 Correct 192 ms 10008 KB Output is correct
32 Correct 201 ms 9888 KB Output is correct
33 Correct 207 ms 10184 KB Output is correct
34 Correct 207 ms 10012 KB Output is correct
35 Correct 133 ms 9948 KB Output is correct
36 Correct 172 ms 9984 KB Output is correct
37 Correct 168 ms 10176 KB Output is correct
38 Correct 212 ms 10008 KB Output is correct
39 Correct 326 ms 12200 KB Output is correct
40 Correct 360 ms 12204 KB Output is correct
41 Correct 298 ms 11996 KB Output is correct
42 Correct 304 ms 11704 KB Output is correct