oj.uz

Submission #98845

# Submission time Handle Problem Language Result Execution time Memory
98845 2019-02-26T14:05:50 Z Just_Solve_The_Problem Highway Tolls (IOI18_highway) C++11
51 / 100
 813 ms 38436 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)1e5 + 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);
	int 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 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 8 ms 7288 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 8 ms 7288 KB Output is correct
4 Correct 8 ms 7288 KB Output is correct
5 Correct 9 ms 7416 KB Output is correct
6 Correct 8 ms 7416 KB Output is correct
7 Correct 8 ms 7416 KB Output is correct
8 Correct 9 ms 7464 KB Output is correct
9 Correct 9 ms 7336 KB Output is correct
10 Correct 8 ms 7316 KB Output is correct
11 Correct 9 ms 7300 KB Output is correct
12 Correct 8 ms 7376 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7600 KB Output is correct
2 Correct 53 ms 9720 KB Output is correct
3 Correct 689 ms 28876 KB Output is correct
4 Correct 666 ms 28652 KB Output is correct
5 Correct 583 ms 28688 KB Output is correct
6 Correct 585 ms 28612 KB Output is correct
7 Correct 571 ms 28588 KB Output is correct
8 Correct 571 ms 28612 KB Output is correct
9 Correct 665 ms 28916 KB Output is correct
10 Correct 579 ms 28588 KB Output is correct
11 Correct 639 ms 30476 KB Output is correct
12 Correct 746 ms 32008 KB Output is correct
13 Correct 589 ms 31000 KB Output is correct
14 Correct 706 ms 31212 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 10640 KB Output is correct
2 Correct 69 ms 13944 KB Output is correct
3 Correct 132 ms 17388 KB Output is correct
4 Correct 304 ms 35008 KB Output is correct
5 Correct 309 ms 34996 KB Output is correct
6 Correct 315 ms 36792 KB Output is correct
7 Correct 341 ms 38436 KB Output is correct
8 Correct 318 ms 35880 KB Output is correct
9 Correct 334 ms 36240 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 7592 KB Output is correct
2 Correct 52 ms 9720 KB Output is correct
3 Correct 421 ms 24104 KB Output is correct
4 Correct 598 ms 28520 KB Output is correct
5 Correct 671 ms 28652 KB Output is correct
6 Correct 587 ms 28732 KB Output is correct
7 Correct 709 ms 28736 KB Output is correct
8 Correct 684 ms 28604 KB Output is correct
9 Correct 655 ms 28904 KB Output is correct
10 Correct 697 ms 28908 KB Output is correct
11 Correct 694 ms 30480 KB Output is correct
12 Correct 591 ms 32264 KB Output is correct
13 Correct 656 ms 31220 KB Output is correct
14 Correct 640 ms 31064 KB Output is correct
15 Correct 569 ms 28592 KB Output is correct
16 Correct 578 ms 28624 KB Output is correct
17 Correct 672 ms 30836 KB Output is correct
18 Correct 695 ms 31772 KB Output is correct
19 Correct 707 ms 28548 KB Output is correct
20 Correct 600 ms 32228 KB Output is correct
21 Correct 568 ms 31096 KB Output is correct
22 Correct 653 ms 31168 KB Output is correct
23 Correct 671 ms 30212 KB Output is correct
24 Correct 660 ms 30588 KB Output is correct
25 Correct 712 ms 38064 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 9844 KB Output is correct
2 Correct 57 ms 10096 KB Output is correct
3 Correct 643 ms 30084 KB Output is correct
4 Incorrect 813 ms 31700 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 57 ms 9916 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -