답안 #98845 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
98845	2019-02-26T14:05:50 Z	Just_Solve_The_Problem	통행료 (IOI18_highway)	C++11	51 / 100	813 ms	38436 KB

highway

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	Grader output
1	Incorrect	57 ms	9916 KB	Output is incorrect: {s, t} is wrong.
2	Halted	0 ms	0 KB	-

답안 #98845

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 7.0 / 7.0

Subtask #3 6.0 / 6.0

Subtask #4 33.0 / 33.0

Subtask #5 0 / 18.0

Subtask #6 0 / 31.0

Subtask #1
5.0 / 5.0

Subtask #2
7.0 / 7.0

Subtask #3
6.0 / 6.0

Subtask #4
33.0 / 33.0

Subtask #5
0 / 18.0

Subtask #6
0 / 31.0