oj.uz

Submission #123661

# Submission time Handle Problem Language Result Execution time Memory
123661 2019-07-01T23:45:20 Z eriksuenderhauf Highway Tolls (IOI18_highway) C++11
100 / 100
 792 ms 14044 KB 
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "highway.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define mem(a,v) memset((a), (v), sizeof (a))
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%I64d", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%I64d\n", (n))
#define pii pair<int, int>
#define pil pair<int, long long>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vil vector<pil>
#define vll vector<pll>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef cc_hash_table<int,int,hash<int>> ht;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MAXN = 130050;
const double eps = 1e-9;
vii adj[MAXN], all;
int n, m, dp[2][MAXN], vis[MAXN];
ll dist;

int solve(int root, int idx) {
	deque<int> pq;
	pq.pb(root);
	vi edg;
	mem(vis, 0);
	vis[root] = 1;
	while (!pq.empty()) {
		int u = pq.front(); pq.pop_front();
		for (pii nx: adj[u]) {
			if (dp[idx][nx.fi] != dp[idx][u] + 1 || vis[nx.fi]) continue;
			vis[nx.fi] = 1;
			pq.pb(nx.fi);
			if (dp[idx][nx.fi] < dp[idx^1][nx.fi])
				edg.pb(nx.fi);
		}
	}
	reverse(edg.begin(), edg.end());
	int lo = 0, hi = edg.size()-1, ans = -1;
	while (lo <= hi) {
		int mi = (lo+hi) / 2;
		vi tmp(m, 0);
		for (int i = 0; i <= mi; i++)
			for (pii nx: adj[edg[i]])
				tmp[nx.se] = 1;
		ll w = ask(tmp);
		if (w == dist)
			lo = mi + 1;
		else {
			ans = mi;
			hi = mi - 1;
		}
		for (int i = 0; i <= mi; i++)
			for (pii nx: adj[edg[i]])
				tmp[nx.se] = 0;
	}
	if (ans == -1) 
		return root;
	return edg[ans];
}

void find_pair(int N, vi U, vi V, int a, int b) {
	n = N;
	m = U.size();
	for (int i = 0; i < m; i++) {
		adj[U[i]].pb(mp(V[i],i));
		adj[V[i]].pb(mp(U[i],i));
		all.pb(mp(U[i], V[i]));
	}
	dist = ask(vi(m, 0));
	int lo = 0, hi = m-1;
	while (lo <= hi) {
		int mi = (lo+hi) / 2;
		vi tmp(m);
		for (int i = 0; i <= mi; i++)
			tmp[i] = 1;
		ll w = ask(tmp);
		if (w == dist)
			lo = mi + 1;
		else
			hi = mi - 1;
	}
	int u = all[lo].fi, v = all[lo].se;
	mem(dp, 0);
	deque<int> pq;
	vis[u] = 1; pq.pb(u);
	while (!pq.empty()) {
		int u2 = pq.front(); pq.pop_front();
		for (pii nx: adj[u2]) {
			if (vis[nx.fi]) continue;
			vis[nx.fi] = 1;
			dp[0][nx.fi] = dp[0][u2] + 1;
			pq.pb(nx.fi);
		}
	}
	mem(vis, 0);
	vis[v] = 1; pq.pb(v);
	while (!pq.empty()) {
		int u2 = pq.front(); pq.pop_front();
		for (pii nx: adj[u2]) {
			if (vis[nx.fi]) continue;
			vis[nx.fi] = 1;
			dp[1][nx.fi] = dp[1][u2] + 1;
			pq.pb(nx.fi);
		}
	}
	int s = solve(u, 0);
	int t = solve(v, 1);
	answer(s, t);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4904 KB Output is correct
2 Correct 7 ms 4800 KB Output is correct
3 Correct 6 ms 4796 KB Output is correct
4 Correct 6 ms 4800 KB Output is correct
5 Correct 6 ms 4792 KB Output is correct
6 Correct 6 ms 4796 KB Output is correct
7 Correct 6 ms 4904 KB Output is correct
8 Correct 6 ms 4856 KB Output is correct
9 Correct 6 ms 4860 KB Output is correct
10 Correct 6 ms 4800 KB Output is correct
11 Correct 6 ms 4880 KB Output is correct
12 Correct 7 ms 4780 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4848 KB Output is correct
2 Correct 39 ms 5652 KB Output is correct
3 Correct 453 ms 11836 KB Output is correct
4 Correct 360 ms 11720 KB Output is correct
5 Correct 444 ms 11832 KB Output is correct
6 Correct 268 ms 11740 KB Output is correct
7 Correct 392 ms 11720 KB Output is correct
8 Correct 533 ms 11736 KB Output is correct
9 Correct 416 ms 11724 KB Output is correct
10 Correct 316 ms 11816 KB Output is correct
11 Correct 533 ms 10884 KB Output is correct
12 Correct 502 ms 11100 KB Output is correct
13 Correct 519 ms 11168 KB Output is correct
14 Correct 549 ms 11248 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 5496 KB Output is correct
2 Correct 50 ms 6236 KB Output is correct
3 Correct 67 ms 6976 KB Output is correct
4 Correct 205 ms 10880 KB Output is correct
5 Correct 189 ms 10872 KB Output is correct
6 Correct 180 ms 11176 KB Output is correct
7 Correct 193 ms 11276 KB Output is correct
8 Correct 186 ms 10828 KB Output is correct
9 Correct 209 ms 11092 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4904 KB Output is correct
2 Correct 38 ms 5592 KB Output is correct
3 Correct 411 ms 10384 KB Output is correct
4 Correct 578 ms 11836 KB Output is correct
5 Correct 656 ms 11728 KB Output is correct
6 Correct 603 ms 11792 KB Output is correct
7 Correct 792 ms 11732 KB Output is correct
8 Correct 661 ms 11780 KB Output is correct
9 Correct 476 ms 11800 KB Output is correct
10 Correct 510 ms 11832 KB Output is correct
11 Correct 490 ms 11168 KB Output is correct
12 Correct 366 ms 11128 KB Output is correct
13 Correct 517 ms 11112 KB Output is correct
14 Correct 543 ms 10808 KB Output is correct
15 Correct 651 ms 11844 KB Output is correct
16 Correct 631 ms 11832 KB Output is correct
17 Correct 452 ms 11148 KB Output is correct
18 Correct 538 ms 11332 KB Output is correct
19 Correct 463 ms 11776 KB Output is correct
20 Correct 450 ms 11212 KB Output is correct
21 Correct 242 ms 11908 KB Output is correct
22 Correct 212 ms 11976 KB Output is correct
23 Correct 271 ms 11660 KB Output is correct
24 Correct 248 ms 11444 KB Output is correct
25 Correct 271 ms 11232 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 5668 KB Output is correct
2 Correct 36 ms 5768 KB Output is correct
3 Correct 334 ms 12188 KB Output is correct
4 Correct 495 ms 12516 KB Output is correct
5 Correct 757 ms 13880 KB Output is correct
6 Correct 620 ms 13660 KB Output is correct
7 Correct 670 ms 13580 KB Output is correct
8 Correct 545 ms 13656 KB Output is correct
9 Correct 335 ms 11872 KB Output is correct
10 Correct 319 ms 12492 KB Output is correct
11 Correct 267 ms 12856 KB Output is correct
12 Correct 481 ms 13140 KB Output is correct
13 Correct 547 ms 13484 KB Output is correct
14 Correct 612 ms 13584 KB Output is correct
15 Correct 702 ms 13596 KB Output is correct
16 Correct 296 ms 12768 KB Output is correct
17 Correct 347 ms 11936 KB Output is correct
18 Correct 437 ms 12140 KB Output is correct
19 Correct 224 ms 12040 KB Output is correct
20 Correct 562 ms 12128 KB Output is correct
21 Correct 697 ms 13948 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 5684 KB Output is correct
2 Correct 34 ms 5776 KB Output is correct
3 Correct 570 ms 11944 KB Output is correct
4 Correct 583 ms 12200 KB Output is correct
5 Correct 583 ms 12504 KB Output is correct
6 Correct 550 ms 13664 KB Output is correct
7 Correct 569 ms 12236 KB Output is correct
8 Correct 676 ms 12524 KB Output is correct
9 Correct 571 ms 12484 KB Output is correct
10 Correct 622 ms 13572 KB Output is correct
11 Correct 653 ms 13568 KB Output is correct
12 Correct 574 ms 13572 KB Output is correct
13 Correct 350 ms 12852 KB Output is correct
14 Correct 311 ms 12508 KB Output is correct
15 Correct 345 ms 12844 KB Output is correct
16 Correct 286 ms 12568 KB Output is correct
17 Correct 337 ms 12920 KB Output is correct
18 Correct 268 ms 12492 KB Output is correct
19 Correct 500 ms 13200 KB Output is correct
20 Correct 655 ms 13524 KB Output is correct
21 Correct 633 ms 13640 KB Output is correct
22 Correct 604 ms 13580 KB Output is correct
23 Correct 649 ms 13472 KB Output is correct
24 Correct 716 ms 13652 KB Output is correct
25 Correct 661 ms 13620 KB Output is correct
26 Correct 646 ms 13560 KB Output is correct
27 Correct 350 ms 12072 KB Output is correct
28 Correct 483 ms 12100 KB Output is correct
29 Correct 519 ms 12308 KB Output is correct
30 Correct 279 ms 12136 KB Output is correct
31 Correct 431 ms 12244 KB Output is correct
32 Correct 414 ms 11972 KB Output is correct
33 Correct 287 ms 12240 KB Output is correct
34 Correct 546 ms 12028 KB Output is correct
35 Correct 418 ms 12148 KB Output is correct
36 Correct 507 ms 11960 KB Output is correct
37 Correct 505 ms 12348 KB Output is correct
38 Correct 244 ms 12188 KB Output is correct
39 Correct 786 ms 14016 KB Output is correct
40 Correct 692 ms 14044 KB Output is correct
41 Correct 358 ms 14004 KB Output is correct
42 Correct 712 ms 13696 KB Output is correct