oj.uz

Submission #98893

# Submission time Handle Problem Language Result Execution time Memory
98893 2019-02-27T07:40:45 Z Just_Solve_The_Problem Highway Tolls (IOI18_highway) C++11
100 / 100
 980 ms 46172 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, s, t;
	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;
	}
	int u, v;
	u = U[r];
	v = V[r];
	queue < int > q;
	q.push(u);
	q.push(v);
	addedge(u, v);
	connect(u, v);
	w[r] = 0;
	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);
	vector < int > ord;
	for (int i = 0; i < n; i++) {
		for (int to : vec[i]) {
			ord.push_back(to);
		}
		vec[i].clear();
	}
	l = -1;
	r = ord.size() - 1;
	while (r - l > 1) {
		int mid = (l + r) >> 1;
		for (int i = 0; i <= mid; i++) {
			w[idc[ord[i]]] = 0;
		}
		ll T = ask(w);
		for (int i = 0; i <= mid; i++) {
			w[idc[ord[i]]] = 1;
		}
		if (T == dist * A) {
			r = mid;
 		} else {
			l = mid;
 		}
	}
	s = ord[r];
	ord.clear();
	h[v] = 0;
	for (int to : del) {
		w[to] = 0;
	}
	del.clear();
	dfs(v, u);
	for (int i = 0; i < n; i++) {
		for (int to : vec[i]) {
			ord.push_back(to);
		}
	}
	l = -1;
	r = ord.size();
	while (r - l > 1) {
		int mid = (l + r) >> 1;
		for (int i = 0; i <= mid; i++) {
			w[idc[ord[i]]] = 0;
		}
		ll T = ask(w);
		for (int i = 0; i <= mid; i++) {
			w[idc[ord[i]]] = 1;
		}
		if (T == dist * A) {
			r = mid;
 		} else {
			l = mid;
 		}
	}
	t = ord[r];
	answer(s, t);
}
/*
8 10 1 2 0 2
0 1
0 2
0 3
1 4
0 5
5 6
2 7
2 3
3 6
5 7


*/

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 14356 KB Output is correct
3 Correct 15 ms 14328 KB Output is correct
4 Correct 15 ms 14328 KB Output is correct
5 Correct 15 ms 14440 KB Output is correct
6 Correct 15 ms 14332 KB Output is correct
7 Correct 15 ms 14408 KB Output is correct
8 Correct 12 ms 14328 KB Output is correct
9 Correct 15 ms 14412 KB Output is correct
10 Correct 15 ms 14328 KB Output is correct
11 Correct 15 ms 14328 KB Output is correct
12 Correct 15 ms 14328 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 14636 KB Output is correct
2 Correct 57 ms 16888 KB Output is correct
3 Correct 647 ms 36312 KB Output is correct
4 Correct 706 ms 36544 KB Output is correct
5 Correct 639 ms 36228 KB Output is correct
6 Correct 678 ms 36232 KB Output is correct
7 Correct 650 ms 36292 KB Output is correct
8 Correct 601 ms 36268 KB Output is correct
9 Correct 586 ms 36252 KB Output is correct
10 Correct 648 ms 36320 KB Output is correct
11 Correct 612 ms 37392 KB Output is correct
12 Correct 625 ms 39360 KB Output is correct
13 Correct 629 ms 38620 KB Output is correct
14 Correct 628 ms 38688 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 17756 KB Output is correct
2 Correct 78 ms 21116 KB Output is correct
3 Correct 105 ms 24856 KB Output is correct
4 Correct 334 ms 42024 KB Output is correct
5 Correct 294 ms 42132 KB Output is correct
6 Correct 317 ms 44424 KB Output is correct
7 Correct 319 ms 46172 KB Output is correct
8 Correct 303 ms 42992 KB Output is correct
9 Correct 327 ms 43696 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 14712 KB Output is correct
2 Correct 58 ms 16680 KB Output is correct
3 Correct 510 ms 31596 KB Output is correct
4 Correct 606 ms 36208 KB Output is correct
5 Correct 575 ms 36312 KB Output is correct
6 Correct 608 ms 36300 KB Output is correct
7 Correct 570 ms 36324 KB Output is correct
8 Correct 582 ms 36224 KB Output is correct
9 Correct 634 ms 36232 KB Output is correct
10 Correct 637 ms 36324 KB Output is correct
11 Correct 633 ms 38188 KB Output is correct
12 Correct 649 ms 39504 KB Output is correct
13 Correct 620 ms 38792 KB Output is correct
14 Correct 620 ms 38184 KB Output is correct
15 Correct 570 ms 36232 KB Output is correct
16 Correct 606 ms 36356 KB Output is correct
17 Correct 666 ms 38256 KB Output is correct
18 Correct 630 ms 38968 KB Output is correct
19 Correct 639 ms 36268 KB Output is correct
20 Correct 620 ms 39832 KB Output is correct
21 Correct 539 ms 38484 KB Output is correct
22 Correct 531 ms 38100 KB Output is correct
23 Correct 563 ms 37184 KB Output is correct
24 Correct 635 ms 37012 KB Output is correct
25 Correct 703 ms 45276 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 16964 KB Output is correct
2 Correct 65 ms 17188 KB Output is correct
3 Correct 739 ms 37700 KB Output is correct
4 Correct 791 ms 39184 KB Output is correct
5 Correct 851 ms 42112 KB Output is correct
6 Correct 878 ms 41860 KB Output is correct
7 Correct 842 ms 41484 KB Output is correct
8 Correct 881 ms 41556 KB Output is correct
9 Correct 608 ms 37700 KB Output is correct
10 Correct 589 ms 37136 KB Output is correct
11 Correct 674 ms 38732 KB Output is correct
12 Correct 791 ms 40024 KB Output is correct
13 Correct 830 ms 40704 KB Output is correct
14 Correct 883 ms 41380 KB Output is correct
15 Correct 884 ms 41880 KB Output is correct
16 Correct 686 ms 37808 KB Output is correct
17 Correct 592 ms 37216 KB Output is correct
18 Correct 591 ms 37356 KB Output is correct
19 Correct 611 ms 37340 KB Output is correct
20 Correct 539 ms 37548 KB Output is correct
21 Correct 820 ms 42624 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 16984 KB Output is correct
2 Correct 67 ms 17108 KB Output is correct
3 Correct 719 ms 37240 KB Output is correct
4 Correct 715 ms 37892 KB Output is correct
5 Correct 714 ms 38704 KB Output is correct
6 Correct 839 ms 41720 KB Output is correct
7 Correct 680 ms 38140 KB Output is correct
8 Correct 697 ms 38568 KB Output is correct
9 Correct 723 ms 38736 KB Output is correct
10 Correct 980 ms 41468 KB Output is correct
11 Correct 843 ms 41636 KB Output is correct
12 Correct 859 ms 41772 KB Output is correct
13 Correct 631 ms 39012 KB Output is correct
14 Correct 594 ms 37332 KB Output is correct
15 Correct 608 ms 38708 KB Output is correct
16 Correct 586 ms 37112 KB Output is correct
17 Correct 628 ms 38720 KB Output is correct
18 Correct 589 ms 37072 KB Output is correct
19 Correct 700 ms 39800 KB Output is correct
20 Correct 823 ms 41220 KB Output is correct
21 Correct 920 ms 41308 KB Output is correct
22 Correct 848 ms 41244 KB Output is correct
23 Correct 888 ms 41424 KB Output is correct
24 Correct 875 ms 41372 KB Output is correct
25 Correct 883 ms 41908 KB Output is correct
26 Correct 871 ms 41956 KB Output is correct
27 Correct 568 ms 37344 KB Output is correct
28 Correct 616 ms 37288 KB Output is correct
29 Correct 575 ms 37604 KB Output is correct
30 Correct 639 ms 37548 KB Output is correct
31 Correct 627 ms 37356 KB Output is correct
32 Correct 536 ms 37188 KB Output is correct
33 Correct 590 ms 37744 KB Output is correct
34 Correct 578 ms 37388 KB Output is correct
35 Correct 583 ms 37324 KB Output is correct
36 Correct 592 ms 37132 KB Output is correct
37 Correct 591 ms 37756 KB Output is correct
38 Correct 670 ms 37976 KB Output is correct
39 Correct 846 ms 43064 KB Output is correct
40 Correct 827 ms 43612 KB Output is correct
41 Correct 854 ms 42728 KB Output is correct
42 Correct 847 ms 41904 KB Output is correct