제출 #1265630

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1265630		uzukishinobu	도로 개발 (JOI15_road_development)	C++20	0 / 100	97 ms	16060 KiB

road_development

#include <bits/stdc++.h>
using namespace std;
int a,b;
struct query{
      int t,l,r;
};
query q[300005];
vector <int> z[200005];
struct dsu{
      int par[200005];
      int sz[200005];
      void init(){
          for (int i=1;i<=a;i++){
               par[i]=i;
               sz[i]=1;
          }
      }
      int find(int u){
          if (par[u]==u){
              return u;
          }
          return par[u]=find(par[u]);
      }
      bool join(int x,int y){
          x=find(x);
          y=find(y);
          if (x==y){
              return false;
          }
          if (sz[x]<sz[y]){
              swap(x,y);
          }
          sz[x]+=sz[y];
          par[y]=x;
          return true;
      }
};
dsu d;

int lead[200005];
int high[200005];
int big[200005];
int head[200005];
int par[200005];
int rev[200005];
int pos[200005];
int curpos;
bool vis[200005];
int child[200005];

void dfs(int i,int parent){
     child[i]=1;
     big[i]=-1;
     vis[i]=true;
     for (auto p:z[i]){
          if (p==parent){
              continue;
          }
          high[p]=high[i]+1;
          dfs(p,i);
          child[i]+=child[p];
          if (big[i]==-1 && child[big[i]]<child[p]){
              big[i]=p;
          }
     }
}
void decompose(int i,int parent,int h){
    curpos++;
    pos[i]=curpos;
    rev[curpos]=i;
    head[i]=h;
    par[i]=parent;

    if (big[i]!=-1){
        decompose(big[i],i,h);
    }
    for (auto p:z[i]){
         if (p==parent || p==big[i]){
             continue;
         }
         decompose(p,i,p);
    }
}
int f[400005];
int lazy[400005];
void push(int id,int l,int r){
    if (lazy[id]!=0){
        lazy[id*2]=lazy[id];
        lazy[id*2+1]=lazy[id];
        int mid=(l+r)/2;
        f[id*2]=(mid-l+1);
        f[id*2+1]=(r-mid);
        lazy[id]=0;
    }
}
void update(int id,int l,int r,int x,int y){
     if (x>r || y<l || f[id]!=0){
         return;
     }
     if (l>=x && y>=r){
         f[id]=(r-l+1);
         lazy[id]=1;
         return;
     }
     int mid=(l+r)/2;
     push(id,l,r);
     update(id*2,l,mid,x,y);
     update(id*2+1,mid+1,r,x,y);
     f[id]=f[id*2]+f[id*2+1];
}
int get(int id,int l,int r,int x,int y){
    if (x>r || y<l){
        return 0;
    }
    if (l>=x && y>=r){
        return f[id];
    }
    int mid=(l+r)/2;
    push(id,l,r);
    return get(id*2,l,mid,x,y)+get(id*2+1,mid+1,r,x,y);
}
void query1(int x,int y){
    int l=x,r=y;
    int cnt=0;
    while (head[x]!=head[y]){
          if (high[head[x]]<high[head[y]]){
              swap(x,y);
          }
          cnt+=get(1,1,curpos,pos[head[x]],pos[x]);
          x=par[head[x]];
    }
    if (high[x]>high[y]){
        swap(x,y);
    }
    cnt+=get(1,1,curpos,pos[x]+1,pos[y]);
    cout << high[l]+high[r]-2*high[x] - cnt << "\n";
}
void query2(int x,int y){

    while (head[x]!=head[y]){
          if (high[head[x]]<high[head[y]]){
              swap(x,y);
          }
          update(1,1,curpos,pos[head[x]],pos[x]);
          x=par[head[x]];
    }
    if (high[x]>high[y]){
        swap(x,y);
    }
    update(1,1,curpos,pos[x]+1,pos[y]);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a >> b;
    d.init();
    for (int i=1;i<=b;i++){
         int c,x,y;
         cin >> c >> x >> y;
         if (c==1){
             if (d.join(x,y)){
                 z[x].push_back(y);
                 z[y].push_back(x);
             }
         }
         q[i]={c,x,y};
    }
    for (int i=1;i<=a;i++){
         if (!vis[i]){
             lead[i]=1;
             dfs(i,0);
         }
    }
    for (int i=1;i<=a;i++){
         if (lead[i]){
             decompose(i,0,i);
         }
    }
    d.init();
    for (int i=1;i<=b;i++){
         auto [c,x,y]=q[i];
         if (c==1){
             if (!d.join(x,y)){
                 query2(x,y);
             }
         }else{
             int l=d.find(x),r=d.find(y);
             if (l!=r){
                 cout << -1 << "\n";
                 continue;
             }
             query1(x,y);
         }
    }
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 25
• Subtask 5: 0 / 15