| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 609598 | 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)
{
}
}
unordered_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) != 0)
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 <= max_d; 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;
}
w.assign(m, 0);
int t = cor[d_t][t_idx];
int cur = t;
while(cur != 0)
{
w[top[cur]] = 1;
cur= sp[cur][0];
}
ll delt = ask(w) - norm;
delt /= (ll)(B - A);
int lca =t;
int avlast = t;
for(int i = 0; i < delt; i ++)
{
avlast= lca;
lca= sp[lca][0];
}
for(int i= 1; i <= max_d; i++)
{
cor[i].clear();
}
for(int i = 0 ; i < n; i++)
{
if(check_sub(i, lca))
{
if(!checksub(i, avlast))
{
cor[d[i]].pb(i);
}
}
}
int d_s = d[lca];
debut = d[lca] + 1;
fin = max_d;
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_s = mid;
debut = mid + 1;
}
else
fin = mid - 1;
}
int s_idx = 0;
debut = 0 ;
fin = (int)(cor[d_s].size()) - 1;
while(debut <= fin)
{
int mid= (debut + fin)/2;
w.assign(m, 0);
for(int i = debut ; i <= mid; i ++)
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);
}