제출 #1260696

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1260696		minhpk	Long Mansion (JOI17_long_mansion)	C++20	100 / 100	256 ms	79256 KiB

long_mansion

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a;
int z[1000005];
vector<int> pos[1000005];

struct dsu{
      int par[1000005];
      int sz[1000005];
      int l[1000005];
      int r[1000005];
      void init(){
           for (int i=1;i<=a;i++){
                par[i]=i;
                sz[i]=1;
                l[i]=i;
                r[i]=i;
           }
      }
      int find(int u){
          if (par[u]==u){
              return u;
          }
          return par[u]=find(par[u]);
      }
      void join(int x,int y){
           x=find(x);
           y=find(y);
           if (x==y){
               return;
           }
           if (sz[x]<sz[y]){
               swap(x,y);
           }
           l[x]=min(l[x],l[y]);
           r[x]=max(r[x],r[y]);
           sz[x]+=sz[y];
           par[y]=x;
      }
};
dsu d;
int vis[1000005];

bool check(int x,int l,int r){
     auto it=lower_bound(pos[x].begin(),pos[x].end(),l);
     if (it!=pos[x].end() && *it<=r){
         return true;
     }
     return false;
}
void dfs(int i,int parent){
     if (vis[i]==2){
         int x=d.find(i);
         int p=d.find(parent);
         d.l[p]=min(d.l[p],d.l[x]);
         d.r[p]=max(d.r[p],d.r[x]);
         return;
     }
     if (vis[i]==1){
         int x=d.find(i);
         int p=d.find(parent);
         d.join(x,p);
         return;
     }
     vis[i]=1;
     while (true){
          int rt=d.find(i);
          int l=d.l[rt];
          int r=d.r[rt];
          bool t=false;
          if (l>1 && check(z[l-1],l,r)){
              dfs(l-1,i);
              t=true;
          }
          if (r+1<=a && check(z[r],l,r)){
              dfs(r+1,i);
              t=true;
          }
          if (!t){
              break;
          }
     }
     vis[i]=2;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a;
    for (int i=1;i<a;i++){
         cin >> z[i];
    }
    for (int i=1;i<=a;i++){
         int c;
         cin >> c;
         while (c--){
               int x;
               cin >> x;
               pos[x].push_back(i);
         }
    }
    d.init();
    for (int i=1;i<=a;i++){
         dfs(i,i);
    }
    int q;
    cin >> q;
    while (q--){
         int x,y;
         cin >> x >> y;
         x=d.find(x);
         if (d.l[x]<=y && y<=d.r[x]){
             cout << "YES\n";
         }else{
             cout << "NO\n";
         }
    }
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 15 / 15
• Subtask 4: 75 / 75