ABC409個人的備忘録[A-E](Fもある) #C++ – Qiita

#include 
using namespace std;
using ll = long long;
templatetypename T> using p_que = priority_queueT,vectorT>,greaterT>>;

//45度回す構造体
struct Mdis{
    ll u,v;

    Mdis(ll x,ll y){
        //45度回すのは足し算と引き算で事足りる
        u = x+y;
        v = x-y;
    }

    ll dist(Mdis const &m){
        //距離を求める関数
        //差の絶対値が大きいほうが距離
        //詳しくは貼った記事を見て
        return max(abs(u - m.u),abs(v - m.v));
    }
};

//長さとその頂点を管理する構造体
struct Len{
    ll len;
    int x,y;

    Len(ll l,int xx,int yy):len(l),x(xx),y(yy){};
};

//普通のUnionFind
struct UnionFind{
    vectorint>par;
    int cnc;
    //連結した回数を管理
    //これが頂点数と同じなら全部連結。    

    UnionFind(int n):par(n){
        for(int i=0;in;i++) par[i] = i;
        cnc = 1;//最初は１
    }

    int root(int n){//親番号を返すやつ
        if(par[n] == n) return n;
        return par[n] = root(par[n]);
    }

    void unite(int n,int m){//くっつけるやつ
        int rn = root(n),rm = root(m);
        if(rn == rm) return;

        par[rn] = rm;
        cnc++;
    }

    bool same(int n,int m){//連結か確認するやつ
        int rn = root(n),rm = root(m);

        if(rn == rm) return true;
        return false;
    }
};

//構造体同士の大小を比べるやつ１
bool operator(const Len &n,const Len &m){
    if(n.len == m.len){
        if(n.x == m.x) return n.y  m.y;
        return n.x  m.x;
    }
    return n.len  m.len;
}

//構造体同士の大小を比べるやつ２
bool operator>(const Len &n,const Len &m){
    if(n.len == m.len){
        if(n.x == m.x) return n.y > m.y;
        return n.x > m.x;
    }
    return n.len > m.len;
}


int main(){
    int n,q;
    cin >> n >> q;

    vectorMdis>pos;
    for(int i=0;in;i++){
        ll x,y;
        cin >> x >> y;

        pos.emplace_back(x,y);//45度回して管理
    }

    p_queLen>que;
    for(int i=0;in;i++){//全ペアの距離を出しqueに入れる
        for(int j=1;jn;j++){
            Len l(0,i,j);
            
            l.len = pos[i].dist(pos[j]);
            que.push(l);
        }
    }

    UnionFind tree(3000);//多めに3000作っておく
    int m = n;
    for(int i=0;iq;i++){
        int c;
        cin >> c;

        if(c == 1){
            ll x,y;
            cin >> x >> y;

            pos.emplace_back(x,y);//新人を追加
            for(int j=0;jm;j++){//新人との距離をすべて出す
                Len l(0,j,m);
                l.len = pos[j].dist(pos[m]);
                
                que.push(l);
            }
            m++;
        }
        if(c == 2){
            if(tree.cnc == m){//全連結なら-1
                cout  "-1"  endl;
            }else{
                ll now = (1LL60);
                while(!que.empty()){
                    if(que.top().len > now) break;//定めた長さより大きいならおしまい
                    auto[len,x,y] = que.top();
                    que.pop();

                    if(tree.same(x,y)) continue;//もう連結ならスキップ
                    now = len;//長さを定める
                    tree.unite(x,y);//くっつける
                }

                cout  now  endl;
            }
        }

        if(c == 3){
            int x,y;
            cin >> x >> y;
            x--,y--;

            //同じか聞く
            if(tree.same(x,y)) cout  "Yes"  endl;
            else cout  "No"  endl;
        }
    }
}