답안 #799414

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
799414	2023-07-31T13:58:10 Z	NothingXD	통행료 (IOI18_highway)	C++17	18 / 100	125 ms	15064 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 = 2;
	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

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	6736 KB	Output is correct
2	Correct	4 ms	6736 KB	Output is correct
3	Correct	3 ms	6736 KB	Output is correct
4	Correct	4 ms	6780 KB	Output is correct
5	Correct	4 ms	6684 KB	Output is correct
6	Correct	3 ms	6684 KB	Output is correct
7	Correct	3 ms	6736 KB	Output is correct
8	Correct	3 ms	6684 KB	Output is correct
9	Correct	4 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

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	6736 KB	Output is correct
2	Correct	14 ms	7392 KB	Output is correct
3	Correct	125 ms	13268 KB	Output is correct
4	Correct	123 ms	13256 KB	Output is correct
5	Correct	121 ms	13276 KB	Output is correct
6	Correct	92 ms	13260 KB	Output is correct
7	Correct	111 ms	13260 KB	Output is correct
8	Correct	124 ms	13264 KB	Output is correct
9	Correct	85 ms	13268 KB	Output is correct
10	Correct	106 ms	13264 KB	Output is correct
11	Correct	85 ms	13124 KB	Output is correct
12	Correct	110 ms	13116 KB	Output is correct
13	Correct	89 ms	13116 KB	Output is correct
14	Correct	102 ms	13128 KB	Output is correct

Subtask #3
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	7424 KB	Output is correct
2	Correct	19 ms	8152 KB	Output is correct
3	Correct	29 ms	8636 KB	Output is correct
4	Correct	74 ms	12880 KB	Output is correct
5	Correct	77 ms	12896 KB	Output is correct
6	Correct	76 ms	12980 KB	Output is correct
7	Correct	64 ms	12544 KB	Output is correct
8	Correct	79 ms	12924 KB	Output is correct
9	Correct	83 ms	12668 KB	Output is correct