| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1048113 | Maite_Morale | Road Closures (APIO21_roads) | 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 <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define vll vector<ll>
#define MAX 500005
#define pll pair<ll,ll>
#define oo 10000000000000
#define F first
#define S second
const ll bts=20;
pll p[MAX],s[bts+10][MAX],t[bts+10][MAX];
vll v[MAX];
ll d[MAX],N;
pll query(ll x,ll y){
if(x>y)return {0,N};
ll c=log2l(abs(x-y)+1);
return max(t[c][x],t[c][y-(1LL<<c)+1]);
}
void dfs(ll x,ll y){
d[x]=d[y]+1;
for(auto w : v[x])dfs(w,x);
}
void init(int n, std::vector<int> h) {
h.push_back(oo);
stack<ll> s1;s1.push(n);
for(int i=0;i<n;i++){
while(h[i]>h[s1.top()]){
p[s1.top()].S=i;
s1.pop();
}
p[i].F=s1.top();
s1.push(i);
}
while(!s1.empty()){p[s1.top()].S=n;s1.pop();}
s[0][n]={n,n};
for(int i=0;i<n;i++){
s[0][i].F=max(pll {h[p[i].F],p[i].F},pll {h[p[i].S],p[i].S}).S;
s[0][i].S=min(pll {h[p[i].F],p[i].F},pll {h[p[i].S],p[i].S}).S;
v[s[0][i].S].push_back(i);
if(p[i].F==n)p[i].F=-1;
//cout<<p[i].F<<" ";
}///cout<<"\n";
dfs(n,n);
for(int i=1;i<=bts;i++){
for(int j=0;j<=n;j++){
s[i][j].F=s[i-1][s[i-1][j].F].F;
s[i][j].S=s[i-1][s[i-1][j].S].S;
//if(i==20)cout<<d[j]<<" ";
//else cout<<s[i][j].S<<" ";
}//cout<<"\n";
}
}
int minimum_jumps(int A, int B, int C, int D) {
swap(B,C);
//cout<<A<<" "<<B<<"\n";
if(A<=p[B].F)return -1;
//cout<<A<<" "<<B<<"\n";
ll r=0;
for(int i=bts;i>=0;i--){
if(d[s[i][A].F]>=d[B]){
r+=(1LL<<i);
A=s[i][A].F;
}
}
for(int i=bts;i>=0;i--){
if(d[s[i][A].S]>=d[B]){
r+=(1LL<<i);
A=s[i][A].S;
}
}
return r;
}