oj.uz

Submission #114929

# Submission time Handle Problem Language Result Execution time Memory
114929 2019-06-04T03:48:49 Z WhipppedCream Highway Tolls (IOI18_highway) C++17
90 / 100
 987 ms 10220 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 vec[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 = F(foo);
	bfs(v); sort(foo.begin(), foo.end(), cmp);
	int T = F(foo);
	bfs(T); sort(foo.begin(), foo.end(), cmp);
	int S = F(foo);
	answer(S, T);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2344 KB Output is correct
2 Correct 4 ms 2424 KB Output is correct
3 Correct 4 ms 2440 KB Output is correct
4 Correct 4 ms 2424 KB Output is correct
5 Correct 4 ms 2444 KB Output is correct
6 Correct 4 ms 2424 KB Output is correct
7 Correct 4 ms 2396 KB Output is correct
8 Correct 4 ms 2424 KB Output is correct
9 Correct 4 ms 2436 KB Output is correct
10 Correct 4 ms 2444 KB Output is correct
11 Correct 4 ms 2324 KB Output is correct
12 Correct 4 ms 2440 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2428 KB Output is correct
2 Correct 26 ms 3088 KB Output is correct
3 Correct 564 ms 8576 KB Output is correct
4 Correct 742 ms 8440 KB Output is correct
5 Correct 609 ms 8460 KB Output is correct
6 Correct 807 ms 8564 KB Output is correct
7 Correct 505 ms 8532 KB Output is correct
8 Correct 445 ms 8464 KB Output is correct
9 Correct 534 ms 8564 KB Output is correct
10 Correct 706 ms 8560 KB Output is correct
11 Correct 400 ms 7916 KB Output is correct
12 Correct 562 ms 7900 KB Output is correct
13 Correct 502 ms 8012 KB Output is correct
14 Correct 598 ms 7912 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3192 KB Output is correct
2 Correct 57 ms 3680 KB Output is correct
3 Correct 97 ms 4320 KB Output is correct
4 Correct 235 ms 8012 KB Output is correct
5 Correct 196 ms 7912 KB Output is correct
6 Correct 243 ms 8028 KB Output is correct
7 Correct 192 ms 7904 KB Output is correct
8 Correct 217 ms 7896 KB Output is correct
9 Correct 195 ms 7892 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2424 KB Output is correct
2 Correct 38 ms 3120 KB Output is correct
3 Correct 234 ms 7044 KB Output is correct
4 Correct 354 ms 8452 KB Output is correct
5 Correct 315 ms 8560 KB Output is correct
6 Correct 338 ms 8516 KB Output is correct
7 Correct 313 ms 8444 KB Output is correct
8 Correct 296 ms 8516 KB Output is correct
9 Correct 683 ms 8476 KB Output is correct
10 Correct 553 ms 8564 KB Output is correct
11 Correct 582 ms 7904 KB Output is correct
12 Correct 782 ms 7908 KB Output is correct
13 Correct 616 ms 8016 KB Output is correct
14 Correct 568 ms 7944 KB Output is correct
15 Correct 343 ms 8452 KB Output is correct
16 Correct 348 ms 8476 KB Output is correct
17 Correct 668 ms 7952 KB Output is correct
18 Correct 513 ms 8020 KB Output is correct
19 Correct 349 ms 8456 KB Output is correct
20 Correct 345 ms 7980 KB Output is correct
21 Correct 517 ms 8820 KB Output is correct
22 Correct 424 ms 8908 KB Output is correct
23 Correct 691 ms 8676 KB Output is correct
24 Correct 709 ms 8644 KB Output is correct
25 Correct 751 ms 8004 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 3152 KB Output is correct
2 Correct 34 ms 3156 KB Output is correct
3 Correct 501 ms 8868 KB Output is correct
4 Correct 613 ms 9172 KB Output is correct
5 Correct 730 ms 10136 KB Output is correct
6 Correct 835 ms 10072 KB Output is correct
7 Correct 758 ms 10044 KB Output is correct
8 Correct 863 ms 10124 KB Output is correct
9 Correct 376 ms 8252 KB Output is correct
10 Correct 315 ms 8740 KB Output is correct
11 Correct 424 ms 9088 KB Output is correct
12 Correct 541 ms 9760 KB Output is correct
13 Correct 653 ms 9876 KB Output is correct
14 Correct 814 ms 10136 KB Output is correct
15 Correct 772 ms 10128 KB Output is correct
16 Correct 487 ms 9420 KB Output is correct
17 Correct 632 ms 8788 KB Output is correct
18 Correct 506 ms 9028 KB Output is correct
19 Correct 475 ms 8888 KB Output is correct
20 Correct 531 ms 8880 KB Output is correct
21 Correct 509 ms 10124 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 3156 KB Output is correct
2 Correct 49 ms 3156 KB Output is correct
3 Correct 363 ms 8812 KB Output is correct
4 Partially correct 695 ms 9064 KB Output is partially correct
5 Partially correct 680 ms 9252 KB Output is partially correct
6 Partially correct 857 ms 10108 KB Output is partially correct
7 Partially correct 410 ms 8820 KB Output is partially correct
8 Partially correct 487 ms 9024 KB Output is partially correct
9 Correct 497 ms 9260 KB Output is correct
10 Partially correct 628 ms 10136 KB Output is partially correct
11 Correct 552 ms 10048 KB Output is correct
12 Partially correct 574 ms 10040 KB Output is partially correct
13 Correct 426 ms 9040 KB Output is correct
14 Correct 374 ms 8816 KB Output is correct
15 Correct 394 ms 9072 KB Output is correct
16 Correct 300 ms 8824 KB Output is correct
17 Correct 420 ms 9176 KB Output is correct
18 Correct 372 ms 8888 KB Output is correct
19 Correct 756 ms 9748 KB Output is correct
20 Correct 469 ms 9988 KB Output is correct
21 Partially correct 804 ms 10148 KB Output is partially correct
22 Correct 747 ms 10020 KB Output is correct
23 Partially correct 987 ms 10048 KB Output is partially correct
24 Correct 664 ms 10120 KB Output is correct
25 Correct 652 ms 10192 KB Output is correct
26 Correct 586 ms 10220 KB Output is correct
27 Correct 610 ms 8968 KB Output is correct
28 Correct 629 ms 8728 KB Output is correct
29 Correct 567 ms 9176 KB Output is correct
30 Correct 648 ms 8820 KB Output is correct
31 Partially correct 610 ms 8840 KB Output is partially correct
32 Partially correct 537 ms 8752 KB Output is partially correct
33 Partially correct 544 ms 9068 KB Output is partially correct
34 Correct 636 ms 8752 KB Output is correct
35 Partially correct 640 ms 8828 KB Output is partially correct
36 Partially correct 561 ms 8756 KB Output is partially correct
37 Partially correct 475 ms 9056 KB Output is partially correct
38 Correct 578 ms 8940 KB Output is correct
39 Correct 603 ms 10116 KB Output is correct
40 Partially correct 612 ms 10148 KB Output is partially correct
41 Partially correct 934 ms 10184 KB Output is partially correct
42 Correct 561 ms 10100 KB Output is correct