Submission #70788

#	Time	Username	Problem	Language	Result	Execution time	Memory
70788		mirbek01	Long Mansion (JOI17_long_mansion)	C++17	0 / 100	70 ms	8824 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 = 2; i <= n; i ++){
            for(int j = 1; j <= n; j ++)
                  p[j] = j, sz[j] = 1, used[j] = 0, vis[j] = 0;
            vis[i] = 1;
            queue <int> q;
            q.push(i);
            while(!q.empty()){
                  int v = q.front();
                  q.pop();
                  for(int j = 0; j < b[v].size(); j ++){
                        int x = b[v][j];
                        if(!used[x]){
                              used[x] = 1;
                              for(auto k : pi[x]){
                                    unite(k.first, k.second);
                              }
                              for(auto k : pi[x]){
                                    if(!vis[k.first] && get(v) == get(k.first)){
                                          vis[k.first] = 1;
                                          q.push(k.first);
                                    }
                                    if(!vis[k.second] && get(v) == get(k.second)){
                                          vis[k.second] = 1;
                                          q.push(k.second);
                                    }
                              }
                        }
                  }
            }
            for(int j = 1; j <= n; j ++){
                  if(get(j) == get(i)) can[i][j] = 1;
            }
      }

      int q;
      cin >> q;

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

Compilation message (stderr)

long_mansion.cpp: In function 'int main()':
long_mansion.cpp:52:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                   for(int j = 0; j < b[v].size(); j ++){
                                  ~~^~~~~~~~~~~~~

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