제출 #651571

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
651571		ymm	Highway Tolls (IOI18_highway)	C++17	51 / 100	312 ms	12056 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 150'010;
int len;
tuple<int,int,int> edges[N];
vector<pii> adj[N];
int n, m;
ll A, B;
mt19937_64 rd(time(0));

namespace dsu
{
	int par[N];
	int rt(int v) {return par[v]==-1?v:(par[v]=rt(par[v]));}
	bool unite(int v, int u)
	{
		v = rt(v);
		u = rt(u);
		if (v == u)
			return 0;
		par[u] = v;
		return 1;
	}
}

ll ask_edge(vector<int> E)
{
	vector<int> vec(m, 0);
	for (int e : E) {
		vec[e] = 1;
	}
	return ask(vec);
}

ll ask_ver(vector<int> V, int l, int r)
{
	vector<int> vec(m, 1);
	Loop (i,0,n)
		for (auto [_, e] : adj[i])
			vec[e] = 0;
	Loop (i,l,r)
		for (auto [_, e] : adj[V[i]])
			vec[e] ^= 1;
	ll tmp =  ask(vec);
	return tmp;
}

ll ask_ver(vector<int> V) { return ask_ver(V, 0, V.size()); }

int bin_search(vector<int> V)
{
	int l = 0, r = V.size();
	while (r - l > 1) {
		int mid = (l+r)/2;
		int par = ((ask_ver(V, l, mid) - A*len) / (B - A)) & 1;
		if (par)
			r = mid;
		else
			l = mid;
	}
	return V[l];
}

void find_pair(int _N, vector<int> _U, vector<int> _V, int _A, int _B)
{
	n = _N; m = _U.size(); A = _A; B = _B;
	Loop (i,0,m)
		edges[i] = {_U[i], _V[i], i};
	len = ask_edge({})/A;
	for (;;) {
		shuffle(edges, edges+m, rd);
		memset(dsu::par, -1, sizeof(dsu::par));
		vector<int> E;
		vector<tuple<int,int,int>> T;
		Loop (i,0,m) {
			auto [v, u, e] = edges[i];
			if (!dsu::unite(v, u))
				E.push_back(e);
			else
				T.push_back(edges[i]);
		}
		if (ask_edge(E) == len*A) {
			for (auto [v, u, e] : T) {
				adj[v].push_back({u, e});
				adj[u].push_back({v, e});
			}
			break;
		}
	}
	vector<int> V;
	for (;;) {
		V.clear();
		Loop (i,0,n)
			if (rd()&1)
				V.push_back(i);
		int par = ((ask_ver(V) - A*len) / (B - A)) & 1;
		if (par)
			break;
	}
	int s = bin_search(V);
	V.resize(n);
	iota(V.begin(), V.end(), 0);
	V.erase(V.begin()+s);
	int t = bin_search(V);
	answer(s, t);
}

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