oj.uz

Submission #159846

# Submission time Handle Problem Language Result Execution time Memory
159846 2019-10-25T02:09:24 Z qkxwsm Highway Tolls (IOI18_highway) C++14
51 / 100
 1409 ms 106376 KB 
#include "highway.h"
#include <bits/stdc++.h>

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
	if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
	if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) ((x).size()))
#define ALL(x) (x).begin(), (x).end()
#define MAXN 90013

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

int N, T, U, V, M;
ll A, B, D;
vi edge[MAXN];
unordered_map<int, int> eid[MAXN];
int st[MAXN], rev[MAXN];
int parent[MAXN];
vi qry;

void dfs(int u, int p)
{
	st[u] = T; rev[T] = u;
	T++;
	for (int v : edge[u])
	{
		if (v == p) continue;
		parent[v] = u;
		dfs(v, u);
	}
}
void find_pair(int n, vi u, vi v, int a, int b)
{
	N = n; A = a; B = b; M = SZ(u); int lo, hi;
	FOR(i, 0, M)
	{
		edge[u[i]].PB(v[i]);
		edge[v[i]].PB(u[i]);
		eid[u[i]][v[i]] = i;
		eid[v[i]][u[i]] = i;
	}
	qry.resize(M); D = ask(qry);
	T = 0;
	dfs(0, N);
	//binary serach on euler tour.
	lo = 0; hi = N;
	while(hi > lo)
	{
		int mid = (hi + lo) >> 1;
		FOR(i, 0, M) qry[i] = 0;
		FOR(i, mid + 1, M)
		{
			int u = rev[i];
			qry[eid[u][parent[u]]] = 1;
		}
		if (ask(qry) == D) hi = mid;
		else lo = mid + 1;
	}
	U = rev[lo];
	T = 0;
	dfs(U, N);
	lo = 0; hi = N;
	while(hi > lo)
	{
		int mid = (hi + lo) >> 1;
		FOR(i, 0, M) qry[i] = 0;
		FOR(i, mid + 1, M)
		{
			int u = rev[i];
			qry[eid[u][parent[u]]] = 1;
		}
		if (ask(qry) == D) hi = mid;
		else lo = mid + 1;
	}
	V = rev[lo];
	// cerr << U << ',' << V << endl;
	answer(U, V);
	//binary search on euler tour twice.
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 8 ms 7464 KB Output is correct
3 Correct 8 ms 7288 KB Output is correct
4 Correct 8 ms 7288 KB Output is correct
5 Correct 22 ms 7456 KB Output is correct
6 Correct 8 ms 7288 KB Output is correct
7 Correct 9 ms 7416 KB Output is correct
8 Correct 9 ms 7416 KB Output is correct
9 Correct 8 ms 7460 KB Output is correct
10 Correct 8 ms 7416 KB Output is correct
11 Correct 8 ms 7288 KB Output is correct
12 Correct 8 ms 7416 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7544 KB Output is correct
2 Correct 56 ms 9000 KB Output is correct
3 Correct 430 ms 22388 KB Output is correct
4 Correct 908 ms 22528 KB Output is correct
5 Correct 1260 ms 22580 KB Output is correct
6 Correct 746 ms 22436 KB Output is correct
7 Correct 487 ms 22576 KB Output is correct
8 Correct 1292 ms 22460 KB Output is correct
9 Correct 868 ms 22512 KB Output is correct
10 Correct 802 ms 22536 KB Output is correct
11 Correct 772 ms 22624 KB Output is correct
12 Correct 1101 ms 23284 KB Output is correct
13 Correct 1060 ms 22620 KB Output is correct
14 Correct 1132 ms 22776 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 9336 KB Output is correct
2 Correct 63 ms 11448 KB Output is correct
3 Correct 91 ms 13480 KB Output is correct
4 Correct 274 ms 25804 KB Output is correct
5 Correct 292 ms 25788 KB Output is correct
6 Correct 239 ms 25792 KB Output is correct
7 Correct 266 ms 25728 KB Output is correct
8 Correct 252 ms 25704 KB Output is correct
9 Correct 272 ms 25700 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7544 KB Output is correct
2 Correct 43 ms 9080 KB Output is correct
3 Correct 316 ms 19100 KB Output is correct
4 Correct 973 ms 22504 KB Output is correct
5 Correct 1124 ms 22564 KB Output is correct
6 Correct 498 ms 22372 KB Output is correct
7 Correct 1061 ms 22468 KB Output is correct
8 Correct 679 ms 22440 KB Output is correct
9 Correct 759 ms 22396 KB Output is correct
10 Correct 1273 ms 22468 KB Output is correct
11 Correct 650 ms 22404 KB Output is correct
12 Correct 968 ms 23160 KB Output is correct
13 Correct 1234 ms 22828 KB Output is correct
14 Correct 1004 ms 23152 KB Output is correct
15 Correct 1409 ms 22544 KB Output is correct
16 Correct 1332 ms 22588 KB Output is correct
17 Correct 540 ms 22868 KB Output is correct
18 Correct 852 ms 23032 KB Output is correct
19 Correct 930 ms 22572 KB Output is correct
20 Correct 991 ms 23500 KB Output is correct
21 Correct 527 ms 22764 KB Output is correct
22 Correct 401 ms 22784 KB Output is correct
23 Correct 461 ms 22800 KB Output is correct
24 Correct 457 ms 23200 KB Output is correct
25 Correct 381 ms 25456 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 165 ms 100216 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 163 ms 106376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -