| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 651570 | ymm | Highway Tolls (IOI18_highway) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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<typeof(*edges)> 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);
}