제출 #1032783

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1032783		AmirAli_H1	통행료 (IOI18_highway)	C++17	90 / 100	185 ms	15596 KiB

highway

// In the name of Allah

#include <bits/stdc++.h>
#include "highway.h"
using namespace std;

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

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 2e5 + 4;
const int oo = 1e9 + 7;

int n, m; ll D;
vector<int> adj[maxn], ls;
vector<pii> E; bool M[maxn];
int arr[maxn], dis[maxn];
queue<int> qu;

void bfs(int v) {
	fill(dis, dis + n, oo);
	dis[v] = 0; qu.push(v);
	while (!qu.empty()) {
		v = qu.front(); qu.pop();
		for (int u : adj[v]) {
			if (dis[v] + 1 < dis[u]) {
				dis[u] = dis[v] + 1;
				qu.push(u);
			}
		}
	}
}

bool cmp(int i, int j) {
	return (dis[i] < dis[j]);
}

ll askx() {
	ls.clear(); ls.resize(m);
	for (int i = 0; i < m; i++) {
		int u = E[i].F, v = E[i].S;
		if (M[u] || M[v]) ls[i] = 1;
		else ls[i] = 0;
	}
	return ask(ls);
}

int getv(vector<int> vc) {
	if (len(vc) == 1) return vc[0];
	
	vector<int> vc1, vc2;
	int mid = (len(vc) / 2);
	for (int i = 0; i < mid; i++) vc1.pb(vc[i]);
	for (int i = mid; i < len(vc); i++) vc2.pb(vc[i]);
	
	for (int u : vc1) M[u] = 1;
	if (askx() == D) return getv(vc2);
	else {
		for (int u : vc1) M[u] = 0;
		return getv(vc1);
	}
}

int getx(int R) {
	iota(arr, arr + n, 0); sort(arr, arr + n, cmp);
	int l = 0, r = n;
	if (R != -1) {
		l = n; r = 0;
		for (int i = 0; i < n; i++) {
			if (dis[arr[i]] == R) {
				l = min(l, i); r = max(r, i + 1);
			}
		}
	}
	
	while (r - l > 1) {
		int mid = (l + r) / 2;
		for (int j = 0; j < n; j++) {
			M[arr[j]] = (j >= mid);
		}
		if (askx() > D) l = mid;
		else r = mid;
	}
	return arr[l];
}

void find_pair(int Nx, vector<int> ux, vector<int> vx, int A, int B) {
	n = Nx; m = len(ux);
	for (int i = 0; i < m; i++) {
		int u = ux[i], v = vx[i];
		adj[u].pb(v); adj[v].pb(u);
		E.pb(Mp(u, v));
	}
	D = askx();
	
	vector<int> vc;
	for (int i = 0; i < n; i++) {
		M[i] = 0; vc.pb(i);
	}
	int vr = getv(vc);
	
	bfs(vr); int u1 = getx(-1);
	bfs(u1); int u2 = getx(D / A);
	answer(u1, u2);
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 6 / 6
• Subtask 4: 33 / 33
• Subtask 5: 18 / 18
• Subtask 6: 21 / 31