| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 743531 | danikoynov | Highway Tolls (IOI18_highway) | C++14 | 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>
using namespace std;
typedef long long ll;
const ll maxn = 2e5 + 10;
vector < pair < ll, ll > > g[maxn];
ll n, m;
ll a, b;
pair < ll, ll > ed[maxn];
vector < int > turn_active(vector < ll > act)
{
vector < int > res(m, 1);
for (ll v : act)
res[v] = 0;
return res;
}
vector < int > turn_inactive(vector < ll > act)
{
vector < int > res(m, 0);
for (ll v : act)
res[v] = 1;
return res;
}
ll mark[maxn], from[maxn], dis[maxn];
ll used[maxn];
ll sub_solve(ll s, vector < ll > st, ll sum)
{
for (ll i = 0; i < n; i ++)
used[i] = 1e9;
for (ll v : st)
used[v] = -1;
used[s] = 0;
queue < ll > q;
q.push(s);
from[s] = -1;
vector < ll > d;
vector < ll > base;
///exit(0);
while(!q.empty())
{
ll v = q.front();
q.pop();
d.push_back(v);
for (pair < ll, ll > nb : g[v])
{
if (used[nb.first] == -1)
{
used[nb.first] = used[v] + 1;
from[nb.first] = nb.second;
base.push_back(nb.second);
q.push(nb.first);
}
}
}
ll lf = 1, rf = (ll)(d.size()) - 1;
while(lf <= rf)
{
ll mf = (lf + rf) / 2;
vector < ll > cur_set;
for (ll i = max((ll)(1),mf); i < d.size(); i ++)
cur_set.push_back(from[d[i]]);
if (ask(turn_inactive(cur_set)) != sum)
lf = mf + 1;
else
rf = mf - 1;
}
return d[rf];
}
void find_pair(ll N, vector<ll> U, vector<ll> V, ll A, ll B)
{
n = N;
m = U.size();
a = A;
b = B;
for (ll i = 0; i < m; i ++)
{
g[U[i]].push_back({V[i], i});
g[V[i]].push_back({U[i], i});
ed[i] = {U[i], V[i]};
}
vector < ll > act;
for (ll i = 0; i < m; i ++)
act.push_back(i);
ll base_sum = ask(turn_active(act));
ll num_edges = base_sum / (ll)(A);
while(act.size() > 1)
{
vector < ll > lf, rf;
for (ll i = 0; i < act.size() / 2; i ++)
lf.push_back(act[i]);
for (ll i = act.size() / 2; i < act.size(); i ++)
rf.push_back(act[i]);
if (ask(turn_active(lf)) != num_edges * (ll)(B))
act = lf;
else
act = rf;
}
ll edge = act[0];
///cout << "here " << edge << endl;
ll v = V[edge], u = U[edge];
queue < ll > q;
mark[v] = 1;
mark[u] = 2;
q.push(v);
q.push(u);
while(!q.empty())
{
ll cur = q.front();
q.pop();
///cout << cur << " : " << mark[cur] << endl;
for (pair < ll, ll > nb : g[cur])
{
if (mark[nb.first] == 0)
{
mark[nb.first] = mark[cur];
q.push(nb.first);
}
}
}
vector < ll > set_s, set_t;
for (ll i = 0; i < n; i ++)
{
if (mark[i] == 1)
set_s.push_back(i);
else
set_t.push_back(i);
}
ll S = sub_solve(v, set_s, base_sum), T = sub_solve(u, set_t, base_sum);
///cout << S << " " << T << " : " << v << " " << u << endl;
answer(S, T);
}