oj.uz

Submission #292711

# Submission time Handle Problem Language Result Execution time Memory
292711 2020-09-07T12:09:44 Z theStaticMind Highway Tolls (IOI18_highway) C++14
51 / 100
 677 ms 262148 KB 
#include<bits/stdc++.h>
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define modulo 1000000007
#define mod 998244353
using namespace std;

#include "highway.h"

vector<int>adj[200000];
vector<int> d;
vector<int> D(200000, 0);
map<ii, int> edge;
vector<int> ptr;

void dfs(int x, int pre, int dep){
	for(auto y : adj[x]){
		if(y == pre) continue;
		d[edge[{x, y}]] = dep;
		D[y] = D[x] + 1;
		dfs(y, x, dep + 1);
	}
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	int M = U.size();
	long long mn = ask(vector<int>(M, 0));

	for(int i = 0; i < M; i++){
		edge[{U[i], V[i]}] = i;
		edge[{V[i], U[i]}] = i;
		ptr.pb(i);
		adj[U[i]].pb(V[i]);
		adj[V[i]].pb(U[i]);
		d.pb(0);
	}

	auto lower = [&](int x){
		D[x] = 0;
		dfs(x, -1, 0);
		sort(all(ptr), [&](int x, int y){return d[x] > d[y];});
		int l = 0, r = M - 1;
		int ret = M - 1;
		while(l <= r){
			int m = (l + r) / 2;
			vector<int> Q(M, 0);
			for(int i = 0; i <= m; i++) Q[ptr[i]] = 1;
			if(ask(Q) != mn){
				ret = m;
				r = m - 1;
			}
			else l = m + 1;
		}
		return ptr[ret];
	};

	int b = 0, e = 0;
	b = lower(0);
	int bb = U[b];
	if(D[V[b]] > D[U[b]]) bb = V[b];

	e = lower(bb);
	int ee = U[e];
	if(D[V[e]] > D[U[e]]) ee = V[e];

	if(bb > ee) swap(bb, ee);

	answer(bb, ee);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6016 KB Output is correct
2 Correct 30 ms 7680 KB Output is correct
3 Correct 437 ms 22532 KB Output is correct
4 Correct 425 ms 22532 KB Output is correct
5 Correct 427 ms 22532 KB Output is correct
6 Correct 410 ms 22532 KB Output is correct
7 Correct 420 ms 22656 KB Output is correct
8 Correct 427 ms 22528 KB Output is correct
9 Correct 426 ms 22620 KB Output is correct
10 Correct 424 ms 22632 KB Output is correct
11 Correct 482 ms 24824 KB Output is correct
12 Correct 485 ms 26308 KB Output is correct
13 Correct 471 ms 25108 KB Output is correct
14 Correct 466 ms 25268 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 8736 KB Output is correct
2 Correct 45 ms 11732 KB Output is correct
3 Correct 66 ms 14712 KB Output is correct
4 Correct 199 ms 32456 KB Output is correct
5 Correct 210 ms 32408 KB Output is correct
6 Correct 185 ms 32288 KB Output is correct
7 Correct 190 ms 32352 KB Output is correct
8 Correct 203 ms 32404 KB Output is correct
9 Correct 200 ms 32304 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6016 KB Output is correct
2 Correct 32 ms 7672 KB Output is correct
3 Correct 305 ms 18944 KB Output is correct
4 Correct 426 ms 22540 KB Output is correct
5 Correct 436 ms 22556 KB Output is correct
6 Correct 426 ms 22620 KB Output is correct
7 Correct 425 ms 22524 KB Output is correct
8 Correct 429 ms 22652 KB Output is correct
9 Correct 419 ms 22528 KB Output is correct
10 Correct 449 ms 22528 KB Output is correct
11 Correct 489 ms 24580 KB Output is correct
12 Correct 470 ms 26040 KB Output is correct
13 Correct 485 ms 25296 KB Output is correct
14 Correct 476 ms 26064 KB Output is correct
15 Correct 420 ms 22536 KB Output is correct
16 Correct 417 ms 22740 KB Output is correct
17 Correct 464 ms 25512 KB Output is correct
18 Correct 482 ms 25708 KB Output is correct
19 Correct 468 ms 22556 KB Output is correct
20 Correct 472 ms 26988 KB Output is correct
21 Correct 363 ms 23052 KB Output is correct
22 Correct 407 ms 22904 KB Output is correct
23 Correct 464 ms 22976 KB Output is correct
24 Correct 483 ms 24012 KB Output is correct
25 Correct 502 ms 31320 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 677 ms 262148 KB Execution killed with signal 9 (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 479 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -