Submission #70794

#	Time	Username	Problem	Language	Result	Execution time	Memory
70794		mirbek01	Long Mansion (JOI17_long_mansion)	C++17	10 / 100	2750 ms	45712 KiB

long_mansion

# include <bits/stdc++.h>

using namespace std;

const int N = 5e3 + 2;

int n, c[N], p[N], sz[N];
bool can[N][N], used[N], vis[N];
vector <int> b[N];
vector < pair <int, int> > pi[N];

int get(int v){
      return (p[v] == v ? v : p[v] = get(p[v]));
}

void unite(int a, int b){
      a = get(a);
      b = get(b);
      if(a != b){
            if(sz[a] < sz[b]) swap(a, b);
            sz[a] += sz[b];
            p[b] = a;
      }
}

int main(){
      cin >> n;

      for(int i = 1; i < n; i ++){
            cin >> c[i];
            pi[c[i]].push_back({i, i + 1});
      }

      for(int i = 1; i <= n; i ++){
            int k, x;
            cin >> k;
            while(k --){
                  cin >> x;
                  b[i].push_back(x);
            }
      }

      for(int i = 1; i <= n; i ++){
            for(int j = 1; j <= n; j ++)
                  used[j] = 0, vis[j] = 0, p[j] = j, sz[j] = 1;
            vector <int> vec;
            vec.push_back(i);
            int mn = i, mx = i;
            while(!vec.empty()){
                  for(int v : vec)
                        used[v] = 1;
                  for(int v : vec){
                        for(int j : b[v]){
                              if(!vis[j]){
                                    vis[j] = 1;
                                    for(auto l : pi[j]){
                                          unite(l.first, l.second);
                                    }
                              }
                        }
                  }
                  vector <int> nw;
                  if(mn - 1 >= 1&& get(mn) == get(mn - 1))
                        nw.push_back(-- mn);
                  if(mx + 1 <= n && get(mx) == get(mx + 1))
                        nw.push_back(++ mx);
                  vec = nw;
            }
            for(int j = 1; j <= n; j ++){
                  can[i][j] = (get(i) == get(j));
            }
      }

      int q;
      cin >> q;

      while(q --){
            int x, y;
            cin >> x >> y;
            if(can[x][y])
                  cout << "YES\n";
            else
                  cout << "NO\n";
      }
}

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