oj.uz

Submission #297229

# Submission time Handle Problem Language Result Execution time Memory
297229 2020-09-11T11:53:38 Z Saboon Highway Tolls (IOI18_highway) C++17
90 / 100
 1006 ms 13672 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
vector<int> Q;
ll Cost = 0;
int p[maxn], par[maxn];
vector<pair<int,int>> g[maxn];
bool mark[maxn];
 
int get(int L, int R){
	if (L+1 == R)
		return L;
	int mid = (L + R) >> 1;
	for (int v = 0; v < mid; v++)
		for (auto [u,idx] : g[v])
			Q[idx] |= 1;
	ll nowCost = ask(Q);
	for (int v = 0; v < mid; v++)
		for (auto [u,idx] : g[v])
			Q[idx] &= 0;
	if (nowCost != Cost)
		return get(L,mid);
	else
		return get(mid,R);
}
 
int Que[maxn], head = 0, tail = 0, h[maxn];
int n;
 
int Get(int v){
	memset(h, -1, sizeof h);
	tail = head = 0;
	h[v] = 0, Que[head++] = v;
	while (tail < head){
		int v = Que[tail++];
		for (auto [u,idx] : g[v])
			if (h[u] == -1)
				h[u] = h[v]+1, Que[head++] = u;
	}
	for (int i = 0; i < n; i++)
		p[i] = i;
	sort(p, p+n, [](int A, int B){
		return h[A] > h[B];
	});
	int L = -1, R = n-1;
	while (R-L > 1){
		int mid = (L+R) >> 1;
		for (int i = 0; i <= mid; i++){
			int v = p[i];
			for (auto [u,idx] : g[v])
				Q[idx] |= 1;
		}
		ll nowCost = ask(Q);
		for (int i = 0; i <= mid; i++){
			int v = p[i];
			for (auto [u,idx] : g[v])
				Q[idx] &= 0;
		}
		if (nowCost == Cost)
			L = mid;
		else
			R = mid;
	}
	return p[R];
}
 
void find_pair(int n, vector<int> U, vector<int> V, int A, int B) {
	::n = n;
	int m = U.size();
	Q.resize(m);
	for (int i = 0; i < m; i++){
		Q[i] = 0;
		g[V[i]].push_back({U[i],i});
		g[U[i]].push_back({V[i],i});
	}
	Cost = ask(Q);
	int v = get(0, n);
	int S = Get(v);
	int T = Get(S);
	answer(S,T);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5888 KB Output is correct
2 Correct 31 ms 6528 KB Output is correct
3 Correct 562 ms 11816 KB Output is correct
4 Correct 352 ms 11912 KB Output is correct
5 Correct 459 ms 11816 KB Output is correct
6 Correct 261 ms 11888 KB Output is correct
7 Correct 614 ms 11788 KB Output is correct
8 Correct 657 ms 11720 KB Output is correct
9 Correct 540 ms 11856 KB Output is correct
10 Correct 355 ms 11736 KB Output is correct
11 Correct 735 ms 11180 KB Output is correct
12 Correct 599 ms 11216 KB Output is correct
13 Correct 705 ms 11288 KB Output is correct
14 Correct 456 ms 11412 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 6400 KB Output is correct
2 Correct 39 ms 7036 KB Output is correct
3 Correct 68 ms 7752 KB Output is correct
4 Correct 185 ms 11168 KB Output is correct
5 Correct 197 ms 11268 KB Output is correct
6 Correct 146 ms 11288 KB Output is correct
7 Correct 202 ms 11272 KB Output is correct
8 Correct 167 ms 11260 KB Output is correct
9 Correct 211 ms 11176 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5888 KB Output is correct
2 Correct 27 ms 6400 KB Output is correct
3 Correct 510 ms 10572 KB Output is correct
4 Correct 795 ms 12060 KB Output is correct
5 Correct 817 ms 11888 KB Output is correct
6 Correct 756 ms 11732 KB Output is correct
7 Correct 848 ms 11876 KB Output is correct
8 Correct 798 ms 11808 KB Output is correct
9 Correct 393 ms 11824 KB Output is correct
10 Correct 577 ms 11856 KB Output is correct
11 Correct 491 ms 11308 KB Output is correct
12 Correct 302 ms 11172 KB Output is correct
13 Correct 535 ms 11204 KB Output is correct
14 Correct 548 ms 11228 KB Output is correct
15 Correct 787 ms 11896 KB Output is correct
16 Correct 756 ms 11740 KB Output is correct
17 Correct 435 ms 11184 KB Output is correct
18 Correct 696 ms 11324 KB Output is correct
19 Correct 808 ms 11824 KB Output is correct
20 Correct 872 ms 11328 KB Output is correct
21 Correct 391 ms 11952 KB Output is correct
22 Correct 348 ms 11972 KB Output is correct
23 Correct 303 ms 11888 KB Output is correct
24 Correct 215 ms 11808 KB Output is correct
25 Correct 242 ms 11256 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 6652 KB Output is correct
2 Correct 32 ms 6520 KB Output is correct
3 Correct 415 ms 12112 KB Output is correct
4 Correct 670 ms 12568 KB Output is correct
5 Correct 757 ms 13548 KB Output is correct
6 Correct 597 ms 13668 KB Output is correct
7 Correct 622 ms 13516 KB Output is correct
8 Correct 614 ms 13484 KB Output is correct
9 Correct 314 ms 11528 KB Output is correct
10 Correct 307 ms 12036 KB Output is correct
11 Correct 388 ms 12256 KB Output is correct
12 Correct 619 ms 13192 KB Output is correct
13 Correct 630 ms 13368 KB Output is correct
14 Correct 677 ms 13476 KB Output is correct
15 Correct 859 ms 13560 KB Output is correct
16 Correct 324 ms 12504 KB Output is correct
17 Correct 353 ms 12156 KB Output is correct
18 Correct 227 ms 12328 KB Output is correct
19 Correct 213 ms 11996 KB Output is correct
20 Correct 274 ms 12232 KB Output is correct
21 Correct 979 ms 13636 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 6528 KB Output is correct
2 Correct 28 ms 6624 KB Output is correct
3 Partially correct 767 ms 12200 KB Output is partially correct
4 Partially correct 594 ms 12292 KB Output is partially correct
5 Correct 452 ms 12532 KB Output is correct
6 Partially correct 613 ms 13528 KB Output is partially correct
7 Partially correct 848 ms 12248 KB Output is partially correct
8 Correct 712 ms 12308 KB Output is correct
9 Partially correct 716 ms 12644 KB Output is partially correct
10 Partially correct 880 ms 13552 KB Output is partially correct
11 Correct 500 ms 13548 KB Output is correct
12 Correct 753 ms 13504 KB Output is correct
13 Correct 346 ms 12156 KB Output is correct
14 Correct 222 ms 12028 KB Output is correct
15 Correct 383 ms 12224 KB Output is correct
16 Correct 396 ms 12048 KB Output is correct
17 Correct 391 ms 12160 KB Output is correct
18 Correct 249 ms 12080 KB Output is correct
19 Correct 545 ms 13096 KB Output is correct
20 Correct 909 ms 13372 KB Output is correct
21 Partially correct 756 ms 13500 KB Output is partially correct
22 Correct 546 ms 13460 KB Output is correct
23 Partially correct 643 ms 13576 KB Output is partially correct
24 Partially correct 679 ms 13528 KB Output is partially correct
25 Correct 592 ms 13456 KB Output is correct
26 Correct 716 ms 13476 KB Output is correct
27 Correct 402 ms 12108 KB Output is correct
28 Partially correct 327 ms 11996 KB Output is partially correct
29 Partially correct 381 ms 12468 KB Output is partially correct
30 Correct 410 ms 12100 KB Output is correct
31 Partially correct 387 ms 12224 KB Output is partially correct
32 Partially correct 267 ms 11956 KB Output is partially correct
33 Correct 359 ms 12352 KB Output is correct
34 Partially correct 320 ms 12020 KB Output is partially correct
35 Correct 413 ms 12040 KB Output is correct
36 Partially correct 231 ms 12020 KB Output is partially correct
37 Correct 289 ms 12244 KB Output is correct
38 Correct 334 ms 12120 KB Output is correct
39 Partially correct 959 ms 13672 KB Output is partially correct
40 Partially correct 1006 ms 13668 KB Output is partially correct
41 Partially correct 329 ms 13536 KB Output is partially correct
42 Correct 796 ms 13548 KB Output is correct