| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 609492 | MohamedAliSaidane | 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 <bits/stdc++.h>
#include "highway.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
#define pb push_back
#define popb pop_back
#define all(x) (x).begin(),(x).end()
#define ff first
#define ss second
const int nax = 9e4 + 4;
vpi adj[nax];
int n, m, a, b;
int d[nax];
vi cor[nax];
int top[nax], sp[nax][20], tin[nax], tout[nax];
int max_d = 1;
int cureul = -1;
/*
ll ask(vi w)
{
return 0;
}
*/
void dfs(int x, int p = 0)
{
sp[x][0] = p;
d[x] = d[p] + 1;
tin[x] = ++cureul;
max_d = max(max_d, d[x]);
cor[d[x]].pb(x);
for(auto e: adj[x])
{
if(e.ff != p)
{
top[e.ff] = e.ss;
dfs(e.ff,x);
}
}
tout[x] = cureul;
}
bool check_sub(int a, int b)
{
if(tin[a] >= tin[b] && tin[a] <= tout[b])
return true;
else
return false;
}
void tle()
{
while(1)
{
}
}
set<int> interd;
void dfs1(int x)
{
interd.insert(x);
for(auto e: adj[x])
{
if(e.ff == sp[x][0])
continue;
if(interd.count(e.ff))
continue;
dfs(e.ff, x);
}
}
void find_pair(int N, vi U, vi V, int A, int B)
{
n = N;
m = U.size();
for(int i = 0 ; i < m; i++)
{
adj[U[i]].pb({V[i], i });
adj[V[i]].pb({U[i], i });
}
dfs(0);
int debut = 2;
int fin = max_d;
vi w(m, 0);
ll norm = ask(w);
int d_t = 2;
while(debut <= fin )
{
int mid = (debut + fin)/2;
w.assign(m, 0);
for(int i = mid; i <= fin; i ++)
{
for(auto e: cor[i])
w[top[e]] = 1;
}
ll cb =ask(w);
if(cb > norm)
{
d_t = mid;
debut = mid +1 ;
}
else
fin = mid - 1;
}
debut = 0;
fin = (int)(cor[d_t].size()) - 1;
int t_idx = 0;
while(debut <= fin)
{
int mid = (debut + fin)/2;
w.assign(m, 0);
for(int i = 0; i <= mid; i ++)
w[top[cor[d_t][i]]] = 1;
ll cb = ask(w);
if(cb > norm)
{
t_idx = mid;
fin = mid - 1;
}
else
debut = mid + 1;
}
int t = cor[d_t][t_idx];
/// 12 Queries for depth of t, 12 queries for t
/// 12 Queries for LCA, 12 queries for depth of s
/// 12 Queries for s
/// Sum = 12 * 5 = 60
int cur = t;
vi ancs;
while(cur != 0)
{
cur = sp[cur][0];
ancs.pb(cur);
}
reverse(all(ancs));
debut= 1;
fin = d_t - 1;
int lca = 0;
while(debut <= fin)
{
int mid = (debut + fin)/2;
w.assign(m, 0);
int pr = ancs[mid];
w[top[pr]] = 1;
ll cb = ask(w);
if(cb == norm)
{
lca = pr;
debut = mid + 1;
}
else
fin = mid -1;
}
debut= d[lca];
fin = d_t;
int d_s = debut;
for(auto e: ancs)
{
if(d[e] > d[lca])
dfs1(e);
}
while(debut <= fin)
{
int mid = (debut + fin)/2;
w.assign(m, 0);
for(int i = mid; i <= fin; i ++)
{
for(auto e: cor[i])
{
if(check_sub(e, lca))
if(interd.count(e) == 0)
w[top[e]] = 1;
}
}
ll cb =ask(w);
if(cb > norm)
{
d_s = mid;
debut = mid +1 ;
}
else
fin = mid - 1;
}
debut = 0;
fin = (int)(cor[d_s].size()) - 1;
int s_idx = 0;
while(debut <= fin)
{
int mid = (debut + fin)/2;
w.assign(m, 0);
for(int i = 0; i <= mid; i ++)
{
if(check_sub(cor[d_s][i], lca))
if(interd.count(cor[d_s][i]]) == 0)
w[top[cor[d_s][i]]] = 1;
}
ll cb = ask(w);
if(cb > norm)
{
s_idx = mid;
fin = mid - 1;
}
else
debut = mid + 1;
}
int s = cor[d_s][s_idx];
answer(s,t);
}