oj.uz

Submission #98891

# Submission time Handle Problem Language Result Execution time Memory
98891 2019-02-27T06:38:32 Z Just_Solve_The_Problem Highway Tolls (IOI18_highway) C++11
0 / 100
 957 ms 42392 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 = 1; i < n; i++) {
		for (int to : vec[i]) {
			ord.push_back(to);
		}
		vec[i].clear();
	}
	vec[0].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);
}
/*
11 16 1 2 0 10
0 1
1 2
0 3
0 4
3 5
2 6
4 7
1 8
7 9
8 10
4 9
2 8
0 4
7 10
0 2
3 7

*/

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14456 KB Output is correct
2 Correct 15 ms 14416 KB Output is correct
3 Correct 16 ms 14484 KB Output is correct
4 Incorrect 16 ms 14456 KB Output is incorrect: {s, t} is wrong.
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 39 ms 29392 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

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

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 14556 KB Output is correct
2 Correct 61 ms 16800 KB Output is correct
3 Incorrect 441 ms 31616 KB Output is incorrect: {s, t} is wrong.
4 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 17020 KB Output is correct
2 Correct 69 ms 17144 KB Output is correct
3 Correct 724 ms 37932 KB Output is correct
4 Correct 885 ms 39376 KB Output is correct
5 Correct 904 ms 42324 KB Output is correct
6 Correct 905 ms 42392 KB Output is correct
7 Correct 868 ms 42200 KB Output is correct
8 Correct 957 ms 42140 KB Output is correct
9 Correct 611 ms 37660 KB Output is correct
10 Incorrect 571 ms 37128 KB Output is incorrect: {s, t} is wrong.
11 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 17016 KB Output is correct
2 Correct 72 ms 17268 KB Output is correct
3 Correct 729 ms 37828 KB Output is correct
4 Correct 780 ms 38380 KB Output is correct
5 Correct 772 ms 39440 KB Output is correct
6 Correct 874 ms 42344 KB Output is correct
7 Correct 700 ms 38020 KB Output is correct
8 Correct 673 ms 38748 KB Output is correct
9 Partially correct 792 ms 39240 KB Output is partially correct
10 Correct 895 ms 42256 KB Output is correct
11 Correct 926 ms 42248 KB Output is correct
12 Partially correct 957 ms 42112 KB Output is partially correct
13 Correct 665 ms 39052 KB Output is correct
14 Incorrect 636 ms 37408 KB Output is incorrect: {s, t} is wrong.
15 Halted 0 ms 0 KB -