Submission #799403

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
799403	2023-07-31T13:54:01 Z	NothingXD	Highway Tolls (IOI18_highway)	C++17	18 / 100	142 ms	15072 KB

highway

#include "highway.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef double ld;
typedef complex<ld> point;

void debug_out(){cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cerr << H << ' ';
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 2e5 + 10;

int n, m, h[maxn], par[maxn], st[maxn], ver[maxn], tme, edge[maxn][2], cnt, sz;
vector<int> g[maxn];
bool mark[maxn];
bool bad[maxn];

void bfs(int V){
	memset(h, -1, sizeof h);
	memset(par, -1, sizeof par);
	memset(mark, true, sizeof mark);
	queue<int> q;
	q.push(V);
	tme = 0;
	h[V] = 0;
	st[V] = 0;
	par[V] = -1;
	ver[0] = V;
	while(!q.empty()){
		int v = q.front();	
		//debug(v, h[v], par[v], st[v], ver[st[v]]);
		q.pop();
		for (auto x: g[v]){
			int u = edge[x][0]^edge[x][1]^v;
			if (!bad[u] && h[u] == -1){
				h[u] = h[v] + 1;
				par[u] = x;
				st[u] = ++tme;
				ver[tme] = u;
				mark[x] = false;
				q.push(u);
			}
		}
	}
	assert(tme == sz-1);
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	n = N;
	m = U.size();
	for (int i = 0; i < m; i++){
		edge[i][0] = U[i];
		edge[i][1] = V[i];
		g[U[i]].push_back(i);
		g[V[i]].push_back(i);
	}

	vector<int> q(m, 0);
	ll dis = ask(q);
	//debug(dis);
	int l = -1, r = n-1;
	int x = 1, y = 3;
	while(l + 1 < r){
		vector<int> q(m, 0);
		int diff = r - l;
		int mid = l + diff * x / y;
		mid = max(mid, l+1);
		//debug(l, r, mid);
		for (int i = 0; i <= mid; i++){
			for (auto x: g[i]){
				q[x] = 1;
			}
		}
		//for (int i = 0; i < m; i++) debug(i, q[i]);
		if (ask(q) == dis) l = mid;
		else r = mid;
	}
	for (int i = 0; i < r; i++){
		bad[i] = true;
	}
	sz = n - r;
//	debug(r);
	bfs(r);
//	for (int i = 0; i < m; i++) debug(i, mark[i]);
	l = 0, r = sz;
	while(l + 1 < r){
		vector<int> q(m, 0);
		int mid = (l + r) >> 1;
	//	debug(mid);
		for (int i = 0; i < m; i++) q[i] = mark[i];
		for (int i = mid; i < sz; i++){
			q[par[ver[i]]] = 1;
		}
	//	for (int i = 0; i < m; i++) debug(i, q[i]);
		if (ask(q) == dis) r = mid;
		else l = mid;
	}
	int S = ver[l];
	bfs(S);
//	debug(S);
//	for (int i = 0; i < m; i++) debug(i, mark[i]);

	l = sz, r = 0;
	for (int i = 0; i < sz; i++){
	//	debug(i, ver[i], h[ver[i]] * A, dis);
		if (1ll * h[ver[i]] * A == dis){
			l = min(l, i);
			r = max(r, i);
		}
	}
	r++;
	while(l + 1 < r){
		vector<int> q(m, 0);
		int mid = (l + r) >> 1;
	//	debug(mid);
		for (int i = 0; i < m; i++) q[i] = mark[i];
		for (int i = mid; i < sz; i++){
			q[par[ver[i]]] = 1;
		}
		//for (int i = 0; i < m; i++) debug(i, q[i]);
		if (ask(q) == dis) r = mid;
		else l = mid;
	}
//	debug(ver[l]);
	answer(S, ver[l]);
}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	6684 KB	Output is correct
2	Correct	3 ms	6684 KB	Output is correct
3	Correct	3 ms	6736 KB	Output is correct
4	Correct	3 ms	6792 KB	Output is correct
5	Correct	3 ms	6736 KB	Output is correct
6	Correct	3 ms	6736 KB	Output is correct
7	Correct	3 ms	6736 KB	Output is correct
8	Correct	3 ms	6684 KB	Output is correct
9	Correct	3 ms	6736 KB	Output is correct
10	Correct	3 ms	6736 KB	Output is correct
11	Correct	3 ms	6736 KB	Output is correct
12	Correct	3 ms	6736 KB	Output is correct

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	6748 KB	Output is correct
2	Correct	12 ms	7392 KB	Output is correct
3	Correct	98 ms	13252 KB	Output is correct
4	Correct	83 ms	13272 KB	Output is correct
5	Correct	138 ms	13284 KB	Output is correct
6	Correct	105 ms	13256 KB	Output is correct
7	Correct	142 ms	13404 KB	Output is correct
8	Correct	92 ms	13260 KB	Output is correct
9	Correct	122 ms	13268 KB	Output is correct
10	Correct	114 ms	13276 KB	Output is correct
11	Correct	82 ms	13112 KB	Output is correct
12	Correct	88 ms	13120 KB	Output is correct
13	Correct	80 ms	13112 KB	Output is correct
14	Correct	94 ms	13112 KB	Output is correct

Subtask #3
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	7384 KB	Output is correct
2	Correct	20 ms	8152 KB	Output is correct
3	Correct	27 ms	8624 KB	Output is correct
4	Correct	73 ms	12884 KB	Output is correct
5	Correct	108 ms	12892 KB	Output is correct
6	Correct	78 ms	12972 KB	Output is correct
7	Correct	76 ms	12536 KB	Output is correct
8	Correct	61 ms	12928 KB	Output is correct
9	Correct	64 ms	12664 KB	Output is correct