This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define svec(x) sort(x.begin(), x.end())
#define press(x) x.erase(unique(x.begin(), x.end()), x.end())
using namespace std;
typedef pair<int, int> pii;
const int inf=1e9;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef cc_hash_table<int, int, hash<int> > ht;
int n, rex, rey;
ht mx[100010], my[100010];
pii p[100010];
vector<int> lx[100010], ly[100010];
bool cmp(pii a, pii b){return mp(a.S, a.F)<mp(b.S, b.F);}
inline void make_tree(){
sort(p+1, p+n+1);
for(int i=1; i<=n; i++){
if(p[i].F!=p[i-1].F||p[i].S!=p[i-1].S+1)rex++;
mx[p[i].F][p[i].S]=rex;
}
sort(p+1, p+n+1, cmp);
for(int i=1; i<=n; i++){
if(p[i].S!=p[i-1].S||p[i].F!=p[i-1].F+1)rey++;
my[p[i].F][p[i].S]=rey;
}
for(int i=1; i<=n; i++){
if(mx[p[i].F+1][p[i].S]){
lx[mx[p[i].F][p[i].S]].eb(mx[p[i].F+1][p[i].S]);
lx[mx[p[i].F+1][p[i].S]].eb(mx[p[i].F][p[i].S]);
}
if(my[p[i].F][p[i].S+1]){
ly[my[p[i].F][p[i].S]].eb(my[p[i].F][p[i].S+1]);
ly[my[p[i].F][p[i].S+1]].eb(my[p[i].F][p[i].S]);
}
}
for(int i=1; i<=rex; i++){
svec(lx[i]);
press(lx[i]);
}
for(int i=1; i<=rey; i++){
svec(ly[i]);
press(ly[i]);
}
}
int sz[100010];
bool ch[100010];
void dfs_x(int num, int par){
sz[num]=1;
for(auto i:lx[num]){
if(i==par||ch[i])continue;
dfs_x(i, num);
sz[num]+=sz[i];
}
}
int get_cen_x(int num, int siz){
int ov=0;
for(auto i:lx[num]){
if(ch[i])continue;
if(sz[i]>siz/2){
ov=i;
break;
}
}
if(!ov)return num;
sz[num]=siz-sz[ov];
sz[ov]=siz;
return get_cen_x(ov, siz);
}
void dfs_y(int num, int par){
sz[num]=1;
for(auto i:ly[num]){
if(i==par||ch[i])continue;
dfs_y(i, num);
sz[num]+=sz[i];
}
}
int get_cen_y(int num, int siz){
int ov=0;
for(auto i:ly[num]){
if(ch[i])continue;
if(sz[i]>siz/2){
ov=i;
break;
}
}
if(!ov)return num;
sz[num]=siz-sz[ov];
sz[ov]=siz;
return get_cen_y(ov, siz);
}
int cpar_x[100010], cpar_y[100010];
int d_x[100010][20], d_y[100010][20];
void make_cen_x(int num, int par){
dfs_x(num, par);
int cen=get_cen_x(num, sz[num]);
cpar_x[cen]=par;
ch[cen]=true;
for(auto i:lx[cen]){
if(ch[i])continue;
make_cen_x(i, cen);
}
}
void make_cen_y(int num, int par){
dfs_y(num, par);
int cen=get_cen_y(num, sz[num]);
cpar_y[cen]=par;
ch[cen]=true;
for(auto i:ly[cen]){
if(ch[i])continue;
make_cen_y(i, cen);
}
}
int dep_x[100010], dep_y[100010];
int sp_x[100010][20], sp_y[100010][20];
void dfs2_x(int num, int par){
dep_x[num]=dep_x[par]+1;
sp_x[num][0]=par;
for(auto i:lx[num]){
if(i==par)continue;
dfs2_x(i, num);
}
}
void dfs2_y(int num, int par){
dep_y[num]=dep_y[par]+1;
sp_y[num][0]=par;
for(auto i:ly[num]){
if(i==par)continue;
dfs2_y(i, num);
}
}
inline int lca_x(int x, int y){
if(dep_x[x]>dep_x[y])swap(x, y);
for(int i=19; i>=0; i--){
if(dep_x[y]-dep_x[x]>=(1<<i))y=sp_x[y][i];
}
if(x==y)return x;
for(int i=19; i>=0; i--){
if(sp_x[x][i]!=sp_x[y][i]){
x=sp_x[x][i];
y=sp_x[y][i];
}
}
return sp_x[x][0];
}
inline int lca_y(int x, int y){
if(dep_y[x]>dep_y[y])swap(x, y);
for(int i=19; i>=0; i--){
if(dep_y[y]-dep_y[x]>=(1<<i))y=sp_y[y][i];
}
if(x==y)return x;
for(int i=19; i>=0; i--){
if(sp_y[x][i]!=sp_y[y][i]){
x=sp_y[x][i];
y=sp_y[y][i];
}
}
return sp_y[x][0];
}
inline int getd_x(int x, int y){return dep_x[x]+dep_x[y]-2*dep_x[lca_x(x, y)];}
inline int getd_y(int x, int y){return dep_y[x]+dep_y[y]-2*dep_y[lca_y(x, y)];}
inline void get_cend_x(){
for(int i=1; i<=rex; i++){
int nw=cpar_x[i];
for(int j=1; nw; j++, nw=cpar_x[nw])d_x[i][j]=getd_x(i, nw);
}
}
inline void get_cend_y(){
for(int i=1; i<=rey; i++){
int nw=cpar_y[i];
for(int j=1; nw; j++, nw=cpar_y[nw])d_y[i][j]=getd_y(i, nw);
}
}
ht arr[100010];
inline void upd(int x, int y){
int nx=mx[x][y], ny=my[x][y];
int tx=nx, ty=ny;
for(int i=0; tx; i++, tx=cpar_x[tx]){
ty=ny;
for(int j=0; ty; j++, ty=cpar_y[ty]){
int tmp=d_x[nx][i]+d_y[ny][j]+1;
if(!arr[tx][ty])arr[tx][ty]=inf;
arr[tx][ty]=min(tmp, arr[tx][ty]);
}
}
}
inline int query(int x, int y){
int nx=mx[x][y], ny=my[x][y], ret=inf;
int tx=nx, ty=ny;
for(int i=0; tx; i++, tx=cpar_x[tx]){
ty=ny;
for(int j=0; ty; j++, ty=cpar_y[ty]){
if(!arr[tx][ty])continue;
int tmp=d_x[nx][i]+d_y[ny][j];
ret=min(ret, arr[tx][ty]+tmp-1);
}
}
return ret==inf?-1:ret;
}
inline int readChar();
template<class T=int> inline T readInt();
static const int buf_size=4096;
inline int getChar(){
static char buf[buf_size];
static int len=0, pos=0;
if(pos==len)pos=0, len=fread(buf, 1, buf_size, stdin);
if(pos==len)return -1;
return buf[pos++];
}
inline int readChar(){
int c=getChar();
while(c<=32)c=getChar();
return c;
}
template <class T>
inline T readInt(){
int s=1, c=readChar();
T x=0;
if(c=='-')s=-1, c=getChar();
while('0'<= c&&c<='9')x=x*10+c-'0', c=getChar();
return s==1?x:-x;
}
int main(){
//scanf("%d", &n);
n=readInt();
for(int i=1; i<=n; i++){
//scanf("%d %d", &p[i].F, &p[i].S);
p[i].F=readInt(); p[i].S=readInt();
}
make_tree();
make_cen_x(1, 0);
memset(ch, 0, sizeof ch);
make_cen_y(1, 0);
dfs2_x(1, 0);
dfs2_y(1, 0);
for(int j=1; j<20; j++){
for(int i=1; i<=rex; i++)sp_x[i][j]=sp_x[sp_x[i][j-1]][j-1];
for(int i=1; i<=rey; i++)sp_y[i][j]=sp_y[sp_y[i][j-1]][j-1];
}
get_cend_x();
get_cend_y();
int q;
//scanf("%d", &q);
q=readInt();
for(int i=1; i<=q; i++){
int a, b, c;
//scanf("%d %d %d", &a, &b, &c);
a=readInt(); b=readInt(); c=readInt();
if(a==1)upd(b, c);
else printf("%d\n", query(b, c));
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |