oj.uz

Submission #98831

# Submission time Handle Problem Language Result Execution time Memory
98831 2019-02-26T10:16:10 Z Just_Solve_The_Problem Highway Tolls (IOI18_highway) C++11
51 / 100
 588 ms 64420 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], idc[maxn];
 
void dfs(int v, int pr) {
	vec[h[v]].push_back(v);
	p[v] = pr;
	idc[v] = mp[{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[idc[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[idc[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 5
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 6 ms 5036 KB Output is correct
2 Correct 6 ms 4984 KB Output is correct
3 Correct 7 ms 5032 KB Output is correct
4 Correct 6 ms 5152 KB Output is correct
5 Correct 6 ms 5020 KB Output is correct
6 Correct 6 ms 5112 KB Output is correct
7 Correct 7 ms 4984 KB Output is correct
8 Correct 6 ms 5028 KB Output is correct
9 Correct 6 ms 4984 KB Output is correct
10 Correct 6 ms 5036 KB Output is correct
11 Correct 6 ms 5112 KB Output is correct
12 Correct 7 ms 5032 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5112 KB Output is correct
2 Correct 65 ms 7028 KB Output is correct
3 Correct 535 ms 22940 KB Output is correct
4 Correct 468 ms 22648 KB Output is correct
5 Correct 441 ms 22600 KB Output is correct
6 Correct 456 ms 22568 KB Output is correct
7 Correct 466 ms 22812 KB Output is correct
8 Correct 460 ms 22556 KB Output is correct
9 Correct 565 ms 22928 KB Output is correct
10 Correct 475 ms 22664 KB Output is correct
11 Correct 526 ms 24440 KB Output is correct
12 Correct 552 ms 25972 KB Output is correct
13 Correct 479 ms 25080 KB Output is correct
14 Correct 577 ms 25320 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 7868 KB Output is correct
2 Correct 43 ms 10712 KB Output is correct
3 Correct 113 ms 13920 KB Output is correct
4 Correct 270 ms 28868 KB Output is correct
5 Correct 274 ms 29016 KB Output is correct
6 Correct 273 ms 30920 KB Output is correct
7 Correct 301 ms 32636 KB Output is correct
8 Correct 275 ms 29848 KB Output is correct
9 Correct 289 ms 30296 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5172 KB Output is correct
2 Correct 58 ms 6920 KB Output is correct
3 Correct 344 ms 18624 KB Output is correct
4 Correct 453 ms 22632 KB Output is correct
5 Correct 569 ms 22708 KB Output is correct
6 Correct 444 ms 22524 KB Output is correct
7 Correct 522 ms 22616 KB Output is correct
8 Correct 532 ms 22676 KB Output is correct
9 Correct 570 ms 22832 KB Output is correct
10 Correct 573 ms 22844 KB Output is correct
11 Correct 536 ms 24480 KB Output is correct
12 Correct 474 ms 26264 KB Output is correct
13 Correct 570 ms 25368 KB Output is correct
14 Correct 523 ms 25068 KB Output is correct
15 Correct 463 ms 22560 KB Output is correct
16 Correct 484 ms 22536 KB Output is correct
17 Correct 567 ms 24800 KB Output is correct
18 Correct 524 ms 25904 KB Output is correct
19 Correct 540 ms 22556 KB Output is correct
20 Correct 511 ms 26356 KB Output is correct
21 Correct 413 ms 23056 KB Output is correct
22 Correct 550 ms 23448 KB Output is correct
23 Correct 507 ms 23348 KB Output is correct
24 Correct 518 ms 24284 KB Output is correct
25 Correct 588 ms 32112 KB Output is correct

Subtask #5
0 / 18.0

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