oj.uz

Submission #98892

# Submission time Handle Problem Language Result Execution time Memory
98892 2019-02-27T07:31:09 Z Just_Solve_The_Problem Highway Tolls (IOI18_highway) C++11
90 / 100
 1010 ms 46248 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[s] = 0;
	for (int to : del) {
		w[to] = 0;
	}
	del.clear();
	dfs(s, s);
	for (int i = 1; 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 14376 KB Output is correct
2 Correct 15 ms 14328 KB Output is correct
3 Correct 15 ms 14456 KB Output is correct
4 Correct 15 ms 14328 KB Output is correct
5 Correct 15 ms 14328 KB Output is correct
6 Correct 15 ms 14328 KB Output is correct
7 Correct 15 ms 14328 KB Output is correct
8 Correct 15 ms 14332 KB Output is correct
9 Correct 15 ms 14328 KB Output is correct
10 Correct 15 ms 14416 KB Output is correct
11 Correct 15 ms 14416 KB Output is correct
12 Correct 15 ms 14376 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 14552 KB Output is correct
2 Correct 57 ms 16876 KB Output is correct
3 Correct 789 ms 36328 KB Output is correct
4 Correct 665 ms 36296 KB Output is correct
5 Correct 649 ms 36272 KB Output is correct
6 Correct 666 ms 36280 KB Output is correct
7 Correct 648 ms 36236 KB Output is correct
8 Correct 601 ms 36340 KB Output is correct
9 Correct 761 ms 36464 KB Output is correct
10 Correct 669 ms 36224 KB Output is correct
11 Correct 690 ms 37864 KB Output is correct
12 Correct 765 ms 39436 KB Output is correct
13 Correct 636 ms 38732 KB Output is correct
14 Correct 837 ms 38652 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 17784 KB Output is correct
2 Correct 74 ms 21212 KB Output is correct
3 Correct 97 ms 24816 KB Output is correct
4 Correct 341 ms 42388 KB Output is correct
5 Correct 326 ms 42392 KB Output is correct
6 Correct 325 ms 44628 KB Output is correct
7 Correct 339 ms 46248 KB Output is correct
8 Correct 330 ms 43504 KB Output is correct
9 Correct 349 ms 43744 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 14632 KB Output is correct
2 Correct 55 ms 16900 KB Output is correct
3 Correct 436 ms 31616 KB Output is correct
4 Correct 589 ms 36244 KB Output is correct
5 Correct 702 ms 36224 KB Output is correct
6 Correct 588 ms 36404 KB Output is correct
7 Correct 710 ms 36388 KB Output is correct
8 Correct 759 ms 36336 KB Output is correct
9 Correct 835 ms 36296 KB Output is correct
10 Correct 756 ms 36324 KB Output is correct
11 Correct 815 ms 38180 KB Output is correct
12 Correct 670 ms 40076 KB Output is correct
13 Correct 773 ms 38772 KB Output is correct
14 Correct 724 ms 38548 KB Output is correct
15 Correct 574 ms 36320 KB Output is correct
16 Correct 562 ms 36312 KB Output is correct
17 Correct 818 ms 38460 KB Output is correct
18 Correct 760 ms 39156 KB Output is correct
19 Correct 707 ms 36328 KB Output is correct
20 Correct 679 ms 39956 KB Output is correct
21 Correct 589 ms 38384 KB Output is correct
22 Correct 638 ms 38464 KB Output is correct
23 Correct 691 ms 37680 KB Output is correct
24 Correct 723 ms 38144 KB Output is correct
25 Correct 902 ms 45560 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 17064 KB Output is correct
2 Correct 71 ms 17304 KB Output is correct
3 Correct 717 ms 38004 KB Output is correct
4 Correct 875 ms 39376 KB Output is correct
5 Correct 876 ms 42348 KB Output is correct
6 Correct 969 ms 42484 KB Output is correct
7 Correct 936 ms 42260 KB Output is correct
8 Correct 967 ms 42184 KB Output is correct
9 Correct 613 ms 37676 KB Output is correct
10 Correct 599 ms 37160 KB Output is correct
11 Correct 735 ms 38848 KB Output is correct
12 Correct 876 ms 40500 KB Output is correct
13 Correct 906 ms 41400 KB Output is correct
14 Correct 982 ms 41964 KB Output is correct
15 Correct 1010 ms 41976 KB Output is correct
16 Correct 784 ms 38080 KB Output is correct
17 Correct 751 ms 37620 KB Output is correct
18 Correct 626 ms 37332 KB Output is correct
19 Correct 696 ms 37732 KB Output is correct
20 Correct 590 ms 37552 KB Output is correct
21 Correct 856 ms 42864 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 17096 KB Output is correct
2 Correct 66 ms 17200 KB Output is correct
3 Correct 749 ms 37936 KB Output is correct
4 Correct 746 ms 38396 KB Output is correct
5 Correct 803 ms 39520 KB Output is correct
6 Correct 948 ms 42248 KB Output is correct
7 Correct 686 ms 38028 KB Output is correct
8 Correct 713 ms 38788 KB Output is correct
9 Partially correct 808 ms 39232 KB Output is partially correct
10 Correct 913 ms 42204 KB Output is correct
11 Partially correct 919 ms 42248 KB Output is partially correct
12 Partially correct 937 ms 42000 KB Output is partially correct
13 Correct 642 ms 39008 KB Output is correct
14 Correct 662 ms 37304 KB Output is correct
15 Correct 619 ms 38744 KB Output is correct
16 Correct 598 ms 37124 KB Output is correct
17 Correct 688 ms 38652 KB Output is correct
18 Correct 527 ms 37080 KB Output is correct
19 Correct 854 ms 40444 KB Output is correct
20 Partially correct 928 ms 41324 KB Output is partially correct
21 Partially correct 864 ms 41896 KB Output is partially correct
22 Correct 952 ms 41824 KB Output is correct
23 Correct 987 ms 42032 KB Output is correct
24 Correct 877 ms 42248 KB Output is correct
25 Correct 917 ms 42024 KB Output is correct
26 Partially correct 951 ms 42076 KB Output is partially correct
27 Correct 719 ms 37632 KB Output is correct
28 Correct 560 ms 37284 KB Output is correct
29 Correct 707 ms 37984 KB Output is correct
30 Partially correct 747 ms 37904 KB Output is partially correct
31 Correct 777 ms 37624 KB Output is correct
32 Correct 746 ms 37620 KB Output is correct
33 Correct 629 ms 37708 KB Output is correct
34 Partially correct 758 ms 37668 KB Output is partially correct
35 Partially correct 679 ms 37664 KB Output is partially correct
36 Correct 548 ms 37224 KB Output is correct
37 Correct 678 ms 38032 KB Output is correct
38 Correct 639 ms 37892 KB Output is correct
39 Correct 824 ms 43344 KB Output is correct
40 Correct 950 ms 43656 KB Output is correct
41 Correct 905 ms 42684 KB Output is correct
42 Correct 928 ms 42364 KB Output is correct