BZOJ 3362: [Usaco2004 Feb]Navigation Nightmare 导航噩梦

时间：2023-03-08 22:01:01

Description

给你每个点与相邻点的距离和方向,求两点间的曼哈顿距离. \(n \leqslant 4\times 10^4\) .

Sol

加权并查集.

像向量合成一样合并就可以了,找 \(f[x]\) 的时候需要先记录现在的父节点,然后更新他新的父节点.

Code

/**************************************************************

    Problem: 3362

    User: BeiYu

    Language: C++

    Result: Accepted

    Time:80 ms

    Memory:3712 kb

****************************************************************/

#include<cstdio>

#include<algorithm>

#include<iostream>

using namespace std;

typedef pair< int,int > pr;

#define abs(x) ((x)<0 ? -(x) : (x) )

#define mpr make_pair

#define debug(a) cout<<#a<<"="<<a<<" "

const int N = 40005;

int n,m,k;

int f[N],ans[N];pr g[N];

struct Q{ int a,b,c,d; }q[N],qq[N];

inline int in(int x=0,char ch=getchar()){ while(ch>'9' || ch<'0') ch=getchar();

    while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x ;}

inline char read(char ch=getchar()){ while(ch>'Z' || ch<'A') ch=getchar();return ch; }

pr operator + (const pr &a,const pr &b){ return mpr(a.first+b.first,a.second+b.second); }

pr operator += (pr &a,const pr &b){ return a=a+b; }

pr operator - (const pr &a,const pr &b){ return mpr(a.first-b.first,a.second-b.second); }

pr operator -= (pr &a,const pr &b){ return a=a-b; }

int cmp1(const Q &x,const Q &y){ return x.c<y.c; }

int cmp2(const Q &x,const Q &y){ return x.d<y.d; }

int find(int x){

    if(f[x] == x) return x;

    int t=f[x];f[x]=find(f[x]);

    g[x]+=g[t];return f[x];

}

void work(int u,int v,int w,char d){

    int r1=find(u),r2=find(v);

//  debug(r1),debug(r2)<<endl;

//  cout<<u<<" "<<v<<" "<<w<<" "<<d<<endl;

//  cout<<"qwq"<<endl;

    if(r1!=r2) switch(d){

        case 'N':f[r1]=r2,g[r1]=g[v]+mpr(0,w)-g[u];break;

        case 'W':f[r1]=r2,g[r1]=g[v]+mpr(-w,0)-g[u];break;

        case 'S':f[r1]=r2,g[r1]=g[v]+mpr(0,-w)-g[u];break;

        default:f[r1]=r2,g[r1]=g[v]+mpr(w,0)-g[u];break;

    }

//  for(int i=1;i<=n;i++) cout<<find(i)<<":("<<g[i].first<<","<<g[i].second<<") ";cout<<endl;

}

int main(){

//  freopen("in.in","r",stdin);

    n=in(),m=in();

    for(int i=1;i<=n;i++) f[i]=i;

    for(int i=1;i<=m;i++) qq[i].a=in(),qq[i].b=in(),qq[i].c=in(),qq[i].d=read();

    k=in();for(int i=1;i<=k;i++) q[i].a=in(),q[i].b=in(),q[i].c=in(),q[i].d=i;

    sort(q+1,q+k+1,cmp1);

//  for(int i=1;i<=m;i++) work(qq[i].a,qq[i].b,qq[i].c,qq[i].d);

//  for(int i=1;i<=n;i++) cout<<find(i)<<" ("<<g[i].first<<","<<g[i].second<<")\n";

    for(int i=1,j=1,u,v,r1,r2;i<=k;i++){

        for(;j<=q[i].c && j<=n;++j) work(qq[j].a,qq[j].b,qq[j].c,qq[j].d);

        u=q[i].a,v=q[i].b,r1=find(u),r2=find(v);

        if(r1==r2){

//          debug(u),debug(v),debug(g[u].first),debug(g[v].first),debug(g[u].second),debug(g[v].second)<<endl;

            ans[q[i].d]=abs(g[u].first-g[v].first)+abs(g[u].second-g[v].second);

        }else ans[q[i].d]=-1;

    }

//  for(int i=1;i<=n;i++) cout<<find(i)<<" ("<<g[i].first<<","<<g[i].second<<")\n";

    for(int i=1;i<=k;i++) printf("%d\n",ans[i]);

    return 0;

}

　　

相关文章