oj.uz

Submission #98847

# Submission time Handle Problem Language Result Execution time Memory
98847 2019-02-26T14:33:54 Z Just_Solve_The_Problem Highway Tolls (IOI18_highway) C++11
51 / 100
 798 ms 45504 KB 
#include "highway.h"
// #include "grader.cpp"
#include <vector>
#include <map>
#include <utility>
#include <iostream>
#include <queue>
 
#define ll long long
 
using namespace std;
 
const int maxn = (int)2e5 + 7;

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

int get(int a) {
	if (id[a] == a) return a;
	return id[a] = get(id[a]);
}

void connect(int a, int b) {
	a = get(a);
	b = get(b);
	id[a] = b;
}

void addedge(int a, int b) {
	nwgr[a].push_back(b);
	nwgr[b].push_back(a);
}
 
void dfs(int v, int pr) {
	vec[h[v]].push_back(v);
	p[v] = pr;
	idc[v] = mp[{v, pr}];
	for (int to : nwgr[v]) {
		if (to == pr) continue;
		h[to] = h[v] + 1;
		del.push_back(mp[{v, to}]);
		w[del.back()] = 1;
		dfs(to, v);
	}
}
 
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
	int n = N;
	int m = U.size();
	ll dist = 0;
	w.resize(m, 0);
	dist = ask(w) / A;
	for (int i = 0; i < n; i++) {
		id[i] = i;
	}
	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;
		}
		ll T = ask(w);
		for (int i = 0; i <= mid; i++) {
			w[i] = 0;
		}
		if (T == dist * A) {
			l = mid;
		} else {
			r = mid;
		}
	}
	for (int i = 0; i < m; i++) {
		w[i] = 1;
	}
	w[r] = 0;
	int u, v;
	u = U[r];
	v = V[r];
	queue < int > q;
	q.push(u);
	q.push(v);
	addedge(u, v);
	connect(u, v);
	while (!q.empty()) {
		int asd = q.front();
		q.pop();
		for (int to : gr[asd]) {
			if (get(to) != get(asd)) {
				addedge(asd, to);
				connect(asd, to);
				w[mp[{asd, to}]] = 0;
				q.push(to);
			}
		}
	}
	dfs(u, v);
	ll asd = (ask(w) - dist * A) / (B - A);
	for (int to : del) {
		w[to] = 0;
	}
	del.clear();
	l = -1;
	r = vec[asd].size() - 1;
	while (r - l > 1) {
		int mid = (l + r) >> 1;
		for (int i = 0; i <= mid; i++) {
			int v = vec[asd][i];
			w[idc[v]] = 1;
		}
		ll T = ask(w);
		for (int i = 0; i <= mid; i++) {
			int v = vec[asd][i];
			w[idc[v]] = 0;
		}
		if (T == dist * A) {
			l = mid;
		} else {
			r = mid;
		}
	}
	int s, t;
	s = vec[asd][r];
	for (int i = 0; i < n; i++) {
		vec[i].clear();
	}
	h[s] = 0;
	dfs(s, s);
	for (int to : del) {
		w[to] = 0;
	}
	asd = dist;
	l = -1;
	r = vec[asd].size() - 1;
	while (r - l > 1) {
		int mid = (l + r) >> 1;
		for (int i = 0; i <= mid; i++) {
			int v = vec[asd][i];
			w[idc[v]] = 1;
		}
		ll T = ask(w);
		for (int i = 0; i <= mid; i++) {
			int v = vec[asd][i];
			w[idc[v]] = 0;
		}
		if (T == dist * A) {
			l = mid;
		} else {
			r = mid;
		}
	}
	t = vec[asd][r];
	answer(s, t);
}
/*
7 7 4 5 4 6
0 2
0 5
1 2
2 3
3 4
4 5
4 6
 
4 4 3 4 2 3
0 1
1 2
2 3
3 0
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14328 KB Output is correct
2 Correct 15 ms 14328 KB Output is correct
3 Correct 15 ms 14372 KB Output is correct
4 Correct 15 ms 14456 KB Output is correct
5 Correct 15 ms 14332 KB Output is correct
6 Correct 15 ms 14328 KB Output is correct
7 Correct 16 ms 14504 KB Output is correct
8 Correct 14 ms 14412 KB Output is correct
9 Correct 14 ms 14416 KB Output is correct
10 Correct 15 ms 14416 KB Output is correct
11 Correct 15 ms 14548 KB Output is correct
12 Correct 15 ms 14500 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 14556 KB Output is correct
2 Correct 63 ms 16892 KB Output is correct
3 Correct 678 ms 35852 KB Output is correct
4 Correct 598 ms 35628 KB Output is correct
5 Correct 587 ms 35764 KB Output is correct
6 Correct 565 ms 35592 KB Output is correct
7 Correct 611 ms 35636 KB Output is correct
8 Correct 604 ms 35680 KB Output is correct
9 Correct 687 ms 36084 KB Output is correct
10 Correct 592 ms 35700 KB Output is correct
11 Correct 654 ms 37360 KB Output is correct
12 Correct 672 ms 38924 KB Output is correct
13 Correct 614 ms 38148 KB Output is correct
14 Correct 675 ms 38292 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 17756 KB Output is correct
2 Correct 74 ms 21096 KB Output is correct
3 Correct 112 ms 24560 KB Output is correct
4 Correct 304 ms 41912 KB Output is correct
5 Correct 321 ms 42060 KB Output is correct
6 Correct 309 ms 43844 KB Output is correct
7 Correct 355 ms 45504 KB Output is correct
8 Correct 313 ms 42952 KB Output is correct
9 Correct 332 ms 43144 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 14632 KB Output is correct
2 Correct 58 ms 16760 KB Output is correct
3 Correct 437 ms 31060 KB Output is correct
4 Correct 567 ms 35544 KB Output is correct
5 Correct 680 ms 35736 KB Output is correct
6 Correct 599 ms 35592 KB Output is correct
7 Correct 688 ms 35576 KB Output is correct
8 Correct 677 ms 35672 KB Output is correct
9 Correct 691 ms 35976 KB Output is correct
10 Correct 705 ms 35968 KB Output is correct
11 Correct 686 ms 37472 KB Output is correct
12 Correct 664 ms 39396 KB Output is correct
13 Correct 664 ms 38224 KB Output is correct
14 Correct 698 ms 38192 KB Output is correct
15 Correct 581 ms 35572 KB Output is correct
16 Correct 568 ms 35848 KB Output is correct
17 Correct 640 ms 37916 KB Output is correct
18 Correct 741 ms 38844 KB Output is correct
19 Correct 684 ms 35600 KB Output is correct
20 Correct 602 ms 39332 KB Output is correct
21 Correct 535 ms 38188 KB Output is correct
22 Correct 698 ms 38124 KB Output is correct
23 Correct 660 ms 37292 KB Output is correct
24 Correct 699 ms 37628 KB Output is correct
25 Correct 741 ms 45108 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 16960 KB Output is correct
2 Correct 69 ms 17064 KB Output is correct
3 Correct 690 ms 37128 KB Output is correct
4 Incorrect 798 ms 38824 KB Output is incorrect: {s, t} is wrong.
5 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 65 ms 16920 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -