oj.uz

Submission #114868

# Submission time Handle Problem Language Result Execution time Memory
114868 2019-06-03T16:13:17 Z WhipppedCream Highway Tolls (IOI18_highway) C++17
51 / 100
 263 ms 25628 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;

vector<ii> adj[maxn];

int ped[maxn];
int dep[maxn];
vector<int> buck[maxn];

int n, m;

void dfs(int u = 0, int p = -1, int d = 0)
{
	dep[u] = d;
	buck[d].pb(u);
	for(auto kk : adj[u])
	{
		int v = kk.X, id = kk.Y;
		if(v == p) continue;
		ped[v] = id;
		dfs(v, u, d+1);
	}
}

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(ii(V[i], i));
		adj[V[i]].pb(ii(U[i], i));
	}

	ll base = ask(vector<int>(m, 0));
	dfs();
	int down = 0;
	for(int i = 0; i< n; i++) down = max(down, dep[i]);
	int lo = 0, hi = down;
	while(lo< hi)
	{
		int mid = (lo+hi+1)/2;
		vector<int> send(m, 0);
		for(int i = mid; i<= down; i++)
		{
			for(int u : buck[i])
			{
				send[ped[u]] = 1;
			}
		}
		ll exp = ask(send);
		// printf("try %d = %lld\n", mid, exp);
		if(exp == base) hi = mid-1;
		else lo = mid;
	}
	int reach = lo;
	// printf("reach = %d\n", reach);	
	lo = 0, hi = ((int) buck[reach].size())-1;
	while(lo< hi)
	{
		int mid = (lo+hi)/2;
		vector<int> send(m, 0);
		for(int i = 0; i<= mid; i++)
		{
			send[ped[buck[reach][i]]] = 1;
		}
		ll exp = ask(send);
		if(exp == base) lo = mid+1;
		else hi = mid;
	}
	int S = buck[reach][lo];
	for(int i = 0; i<= down; i++) buck[i].clear();
	ped[S] = -1;
	dfs(S, -1, 0);
	int reach2 = base/A;
	lo = 0, hi = ((int) buck[reach2].size())-1;
	// for(int i = 0; i< n; i++) printf("ped[%d] = %d\n", i, ped[i]);
	while(lo< hi)
	{
		int mid = (lo+hi)/2;
		vector<int> send(m, 0);
		for(int i = 0; i<= mid; i++)
		{
			send[ped[buck[reach2][i]]] = 1;
		}
		ll exp = ask(send);
		if(exp == base) lo = mid+1;
		else hi = mid;
	}
	int T = buck[reach2][lo];
	answer(S, T);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4472 KB Output is correct
2 Correct 6 ms 4600 KB Output is correct
3 Correct 6 ms 4604 KB Output is correct
4 Correct 6 ms 4600 KB Output is correct
5 Correct 6 ms 4472 KB Output is correct
6 Correct 6 ms 4556 KB Output is correct
7 Correct 5 ms 4552 KB Output is correct
8 Correct 6 ms 4548 KB Output is correct
9 Correct 6 ms 4600 KB Output is correct
10 Correct 6 ms 4548 KB Output is correct
11 Correct 6 ms 4600 KB Output is correct
12 Correct 6 ms 4552 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4600 KB Output is correct
2 Correct 34 ms 5264 KB Output is correct
3 Correct 263 ms 11128 KB Output is correct
4 Correct 199 ms 11120 KB Output is correct
5 Correct 201 ms 11192 KB Output is correct
6 Correct 209 ms 11052 KB Output is correct
7 Correct 218 ms 11236 KB Output is correct
8 Correct 222 ms 11324 KB Output is correct
9 Correct 216 ms 11428 KB Output is correct
10 Correct 216 ms 11084 KB Output is correct
11 Correct 230 ms 12004 KB Output is correct
12 Correct 237 ms 12784 KB Output is correct
13 Correct 246 ms 12020 KB Output is correct
14 Correct 203 ms 12344 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 6052 KB Output is correct
2 Correct 41 ms 7388 KB Output is correct
3 Correct 48 ms 8808 KB Output is correct
4 Correct 155 ms 17352 KB Output is correct
5 Correct 145 ms 17372 KB Output is correct
6 Correct 171 ms 17360 KB Output is correct
7 Correct 170 ms 17348 KB Output is correct
8 Correct 174 ms 17364 KB Output is correct
9 Correct 132 ms 17400 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4600 KB Output is correct
2 Correct 27 ms 5352 KB Output is correct
3 Correct 138 ms 9768 KB Output is correct
4 Correct 182 ms 11016 KB Output is correct
5 Correct 159 ms 10928 KB Output is correct
6 Correct 218 ms 11176 KB Output is correct
7 Correct 163 ms 11160 KB Output is correct
8 Correct 198 ms 10936 KB Output is correct
9 Correct 180 ms 11040 KB Output is correct
10 Correct 198 ms 11068 KB Output is correct
11 Correct 208 ms 11988 KB Output is correct
12 Correct 213 ms 12684 KB Output is correct
13 Correct 260 ms 12320 KB Output is correct
14 Correct 251 ms 12788 KB Output is correct
15 Correct 175 ms 10988 KB Output is correct
16 Correct 188 ms 10964 KB Output is correct
17 Correct 217 ms 12452 KB Output is correct
18 Correct 254 ms 12572 KB Output is correct
19 Correct 160 ms 11272 KB Output is correct
20 Correct 233 ms 13208 KB Output is correct
21 Correct 180 ms 11640 KB Output is correct
22 Correct 241 ms 11612 KB Output is correct
23 Correct 197 ms 11120 KB Output is correct
24 Correct 220 ms 12068 KB Output is correct
25 Correct 202 ms 16740 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 54 ms 25628 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 51 ms 25508 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -