oj.uz

Submission #114937

# Submission time Handle Problem Language Result Execution time Memory
114937 2019-06-04T04:28:44 Z WhipppedCream Highway Tolls (IOI18_highway) C++17
90 / 100
 954 ms 10240 KB 
#include <bits/stdc++.h>
#include "highway.h"
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;

const int maxn = 9e4+5;

ll base;

int n, m;

vector< ii > adj[maxn];

int dist[maxn];

void bfs(int s)
{
	for(int i = 0; i< n; i++) dist[i] = 1e9;
	dist[s] = 0;
	queue<int> q; q.push(s);
	while(!q.empty())
	{
		int u = q.front(); q.pop();
		for(auto kk : adj[u])
		{
			int v = kk.X;
			if(dist[v]> dist[u]+1)
			{
				dist[v] = dist[u]+1;
				q.push(v);
			}
		}
	}
}

bool cmp(int a, int b)
{
	return dist[a]< dist[b];
}

int F(vector<int> &vec)
{
	int lo = 0, hi = n-1;
	while(lo< hi)
	{
		int mid = (lo+hi)/2;
		vector<bool> mark(n, false);
		vector<int> send(m, 1);
		for(int i = 0; i<= mid; i++) mark[vec[i]] = true;
		for(int i = 0; i<= mid; i++)
		{
			int u = vec[i];
			for(auto kk : adj[u])
			{
				int v = kk.X, id = kk.Y;
				if(mark[u] && mark[v])
				{
					send[id] = 0;
				}
			}
		}
		ll exp = ask(send);
		if(exp == base) hi = mid;
		else lo = mid+1;
	}
	return lo;
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B)
{
	n = N;
	m = U.size();
	for(int i = 0; i< m; i++)
	{
		adj[U[i]].pb({V[i], i});
		adj[V[i]].pb({U[i], i});
	}
	base = ask(vector<int>(m, 0));
	vector<int> foo;
	for(int i = 0; i< n; i++) foo.pb(i);
	int v = foo[F(foo)];
	bfs(v); sort(foo.begin(), foo.end(), cmp);
	int ad = F(foo);
	int T = foo[ad];
	foo.erase(foo.begin()+ad+1, foo.end());
	bfs(T); sort(foo.begin(), foo.end(), cmp);
	int S = foo[F(foo)];
	answer(S, T);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2424 KB Output is correct
2 Correct 22 ms 3120 KB Output is correct
3 Correct 557 ms 8464 KB Output is correct
4 Correct 680 ms 8548 KB Output is correct
5 Correct 619 ms 8568 KB Output is correct
6 Correct 717 ms 8520 KB Output is correct
7 Correct 362 ms 8468 KB Output is correct
8 Correct 414 ms 8448 KB Output is correct
9 Correct 331 ms 8536 KB Output is correct
10 Correct 672 ms 8464 KB Output is correct
11 Correct 367 ms 7992 KB Output is correct
12 Correct 500 ms 8016 KB Output is correct
13 Correct 478 ms 7960 KB Output is correct
14 Correct 620 ms 8008 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3120 KB Output is correct
2 Correct 41 ms 3676 KB Output is correct
3 Correct 62 ms 4268 KB Output is correct
4 Correct 209 ms 7892 KB Output is correct
5 Correct 200 ms 8016 KB Output is correct
6 Correct 232 ms 7972 KB Output is correct
7 Correct 182 ms 7900 KB Output is correct
8 Correct 253 ms 7916 KB Output is correct
9 Correct 234 ms 7912 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2424 KB Output is correct
2 Correct 24 ms 3120 KB Output is correct
3 Correct 247 ms 7124 KB Output is correct
4 Correct 374 ms 8452 KB Output is correct
5 Correct 351 ms 8556 KB Output is correct
6 Correct 311 ms 8448 KB Output is correct
7 Correct 314 ms 8456 KB Output is correct
8 Correct 322 ms 8548 KB Output is correct
9 Correct 590 ms 8536 KB Output is correct
10 Correct 497 ms 8548 KB Output is correct
11 Correct 572 ms 7900 KB Output is correct
12 Correct 755 ms 8020 KB Output is correct
13 Correct 544 ms 8020 KB Output is correct
14 Correct 515 ms 8016 KB Output is correct
15 Correct 336 ms 8468 KB Output is correct
16 Correct 332 ms 8540 KB Output is correct
17 Correct 617 ms 7952 KB Output is correct
18 Correct 519 ms 7940 KB Output is correct
19 Correct 313 ms 8532 KB Output is correct
20 Correct 336 ms 7992 KB Output is correct
21 Correct 486 ms 8804 KB Output is correct
22 Correct 358 ms 8744 KB Output is correct
23 Correct 633 ms 8704 KB Output is correct
24 Correct 577 ms 8644 KB Output is correct
25 Correct 778 ms 7988 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 3116 KB Output is correct
2 Correct 29 ms 3160 KB Output is correct
3 Correct 474 ms 8796 KB Output is correct
4 Correct 545 ms 9184 KB Output is correct
5 Correct 626 ms 10140 KB Output is correct
6 Correct 815 ms 10156 KB Output is correct
7 Correct 629 ms 10132 KB Output is correct
8 Correct 774 ms 10040 KB Output is correct
9 Correct 383 ms 8240 KB Output is correct
10 Correct 313 ms 8812 KB Output is correct
11 Correct 410 ms 9008 KB Output is correct
12 Correct 427 ms 9772 KB Output is correct
13 Correct 667 ms 9852 KB Output is correct
14 Correct 837 ms 10056 KB Output is correct
15 Correct 745 ms 10088 KB Output is correct
16 Correct 469 ms 9348 KB Output is correct
17 Correct 497 ms 8780 KB Output is correct
18 Correct 424 ms 8976 KB Output is correct
19 Correct 396 ms 8824 KB Output is correct
20 Correct 391 ms 8824 KB Output is correct
21 Correct 465 ms 10128 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 3200 KB Output is correct
2 Correct 68 ms 3168 KB Output is correct
3 Partially correct 328 ms 8808 KB Output is partially correct
4 Partially correct 632 ms 9056 KB Output is partially correct
5 Partially correct 688 ms 9264 KB Output is partially correct
6 Correct 827 ms 10056 KB Output is correct
7 Correct 382 ms 8800 KB Output is correct
8 Partially correct 414 ms 9004 KB Output is partially correct
9 Correct 398 ms 9264 KB Output is correct
10 Partially correct 474 ms 10100 KB Output is partially correct
11 Correct 478 ms 10064 KB Output is correct
12 Correct 422 ms 10080 KB Output is correct
13 Correct 449 ms 9020 KB Output is correct
14 Correct 348 ms 8752 KB Output is correct
15 Correct 386 ms 9200 KB Output is correct
16 Correct 342 ms 8732 KB Output is correct
17 Correct 396 ms 9108 KB Output is correct
18 Correct 355 ms 8816 KB Output is correct
19 Correct 699 ms 9736 KB Output is correct
20 Correct 406 ms 9892 KB Output is correct
21 Partially correct 685 ms 10096 KB Output is partially correct
22 Correct 674 ms 10132 KB Output is correct
23 Correct 870 ms 10036 KB Output is correct
24 Partially correct 459 ms 10040 KB Output is partially correct
25 Correct 491 ms 10092 KB Output is correct
26 Partially correct 476 ms 10056 KB Output is partially correct
27 Correct 496 ms 8800 KB Output is correct
28 Correct 573 ms 8908 KB Output is correct
29 Correct 512 ms 9080 KB Output is correct
30 Correct 710 ms 8840 KB Output is correct
31 Correct 582 ms 8884 KB Output is correct
32 Partially correct 403 ms 8716 KB Output is partially correct
33 Partially correct 551 ms 9000 KB Output is partially correct
34 Correct 589 ms 8884 KB Output is correct
35 Partially correct 641 ms 8872 KB Output is partially correct
36 Partially correct 439 ms 8744 KB Output is partially correct
37 Partially correct 440 ms 9076 KB Output is partially correct
38 Partially correct 507 ms 8908 KB Output is partially correct
39 Correct 566 ms 10208 KB Output is correct
40 Partially correct 554 ms 10240 KB Output is partially correct
41 Partially correct 954 ms 10156 KB Output is partially correct
42 Correct 537 ms 10212 KB Output is correct