oj.uz

Submission #98829

# Submission time Handle Problem Language Result Execution time Memory
98829 2019-02-26T10:12:07 Z Just_Solve_The_Problem Highway Tolls (IOI18_highway) C++11
18 / 100
 1500 ms 64336 KB 
#include "highway.h"
//#include "grader.cpp"
#include <vector>
#include <map>
#include <utility>
#include <iostream>

#define ll long long

using namespace std;

const int maxn = (int)1e5 + 7;

int h[maxn];
vector < int > gr[maxn];
vector < int > vec[maxn];
vector < int > w;
map < pair < int, int >, int > mp;
int p[maxn];

void dfs(int v, int pr) {
	vec[h[v]].push_back(v);
	p[v] = pr;
	for (int to : gr[v]) {
		if (to == pr) continue;
		h[to] = h[v] + 1;
		w[mp[{v, to}]] = 1;
		dfs(to, v);
	}
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
	int m = U.size();
	ll dist = 0;
	w.resize(m, 0);
	dist = ask(w) / A;
	for (int i = 0; i < m; i++) {
		int u, v;
		u = U[i];
		v = V[i];
		mp[{v, u}] = mp[{u, v}] = i;
		gr[u].push_back(v);
		gr[v].push_back(u);
	}
	int l = -1;
	int r = m - 1;
	while (r - l > 1) {
		int mid = (l + r) >> 1;
		for (int i = 0; i <= mid; i++) {
			w[i] = 1;
		}
		for (int i = mid + 1; i < m; i++) {
			w[i] = 0;
		}
		ll T = ask(w);
		if (T > dist * A) {
			r = mid;
		} else {
			l = mid;
		}
	}
	int a, b;
	a = U[r];
	b = V[r];
	for (int i = 0; i < m; i++) {
		w[i] = 0;
	}
	dfs(a, b);
	int s, t;
	ll asd = (ask(w) - dist * A) / (B - A);
	l = -1;
	r = vec[asd].size() - 1;
	while (r - l > 1) {
		int mid = (l + r) >> 1, v;
		for (int i = 0; i < m; i++) {
			w[i] = 0;
		}
		for (int i = 0; i <= mid; i++) {
			v = vec[asd][i];
			w[mp[{v, p[v]}]] = 1;
		}
		ll T = ask(w);
		if (T > A * dist) {
			r = mid;
		} else {
			l = mid;
		}
	}
	s = vec[asd][r];
	for (int i = 0; i < maxn; i++) {
		vec[i].clear();
	}
	h[s] = 0;
	dfs(s, s);
	asd = dist;
	l = -1;
	r = vec[asd].size() - 1;
	while (r - l > 1) {
		int mid = (l + r) >> 1, v;
		for (int i = 0; i < m; i++) {
			w[i] = 0;
		}
		for (int i = 0; i <= mid; i++) {
			v = vec[asd][i];
			w[mp[{v, p[v]}]] = 1;
		}
		ll T = ask(w);
		if (T > A * dist) {
			r = mid;
		} else {
			l = mid;
		}
	}
	t = vec[asd][r];
	answer(s, t);
}
/*
7 6 4 5 0 3
0 2
1 2
2 3
3 4
4 5
4 6

2 1 1 2 0 1
0 1
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4984 KB Output is correct
2 Correct 6 ms 5020 KB Output is correct
3 Correct 7 ms 5112 KB Output is correct
4 Correct 6 ms 4988 KB Output is correct
5 Correct 6 ms 5104 KB Output is correct
6 Correct 6 ms 4984 KB Output is correct
7 Correct 6 ms 4984 KB Output is correct
8 Correct 7 ms 5040 KB Output is correct
9 Correct 7 ms 5112 KB Output is correct
10 Correct 7 ms 5036 KB Output is correct
11 Correct 6 ms 5040 KB Output is correct
12 Correct 7 ms 5112 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5292 KB Output is correct
2 Correct 44 ms 6904 KB Output is correct
3 Correct 730 ms 22608 KB Output is correct
4 Correct 481 ms 22268 KB Output is correct
5 Correct 489 ms 22228 KB Output is correct
6 Correct 440 ms 22204 KB Output is correct
7 Correct 523 ms 22248 KB Output is correct
8 Correct 479 ms 22252 KB Output is correct
9 Correct 540 ms 22584 KB Output is correct
10 Correct 515 ms 22252 KB Output is correct
11 Correct 512 ms 23996 KB Output is correct
12 Correct 531 ms 25688 KB Output is correct
13 Correct 457 ms 24712 KB Output is correct
14 Correct 523 ms 24964 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 7856 KB Output is correct
2 Correct 77 ms 10676 KB Output is correct
3 Correct 128 ms 13876 KB Output is correct
4 Correct 264 ms 28640 KB Output is correct
5 Correct 253 ms 28572 KB Output is correct
6 Correct 256 ms 30636 KB Output is correct
7 Correct 261 ms 32252 KB Output is correct
8 Correct 255 ms 29456 KB Output is correct
9 Correct 270 ms 29848 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5176 KB Output is correct
2 Correct 41 ms 6888 KB Output is correct
3 Correct 305 ms 18372 KB Output is correct
4 Correct 485 ms 22320 KB Output is correct
5 Correct 477 ms 22392 KB Output is correct
6 Correct 425 ms 22132 KB Output is correct
7 Correct 475 ms 22156 KB Output is correct
8 Correct 478 ms 22300 KB Output is correct
9 Correct 562 ms 22528 KB Output is correct
10 Correct 562 ms 22508 KB Output is correct
11 Correct 503 ms 24132 KB Output is correct
12 Correct 445 ms 25984 KB Output is correct
13 Correct 489 ms 25008 KB Output is correct
14 Correct 495 ms 24708 KB Output is correct
15 Correct 446 ms 22224 KB Output is correct
16 Correct 433 ms 22144 KB Output is correct
17 Correct 526 ms 24408 KB Output is correct
18 Correct 556 ms 25544 KB Output is correct
19 Correct 524 ms 22264 KB Output is correct
20 Correct 461 ms 25984 KB Output is correct
21 Correct 808 ms 22676 KB Output is correct
22 Execution timed out 1541 ms 23084 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

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