Submission #370067

#	Time	Username	Problem	Language	Result	Execution time	Memory
370067		Mamnoon_Siam	Long Mansion (JOI17_long_mansion)	C++17	0 / 100	3067 ms	5684 KiB

long_mansion

#include <bits/stdc++.h>
using namespace std;

/* sorry, this is the bare minimum :'( */
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
#define all(v) begin(v), end(v)
#define sz(v) (int)(v).size()
#define fi first
#define se second

int main(int argc, char const *argv[])
{
  cin.sync_with_stdio(0); cin.tie(0);
  cin.exceptions(cin.failbit);
#ifdef LOCAL
  freopen("in", "r", stdin);
#endif
  int n; cin >> n;
  vi C(n-1);
  for(int i = 0; i < n-1; ++i) {
    cin >> C[i];
    C[i]--;
  }
  using bs = bitset<50>;
  vector<bs> A(n);
  for(int i = 0; i < n; ++i) {
    int k; cin >> k;
    while(k--) {
      int x; cin >> x;
      x--;
      A[i][x] = 1;
    }
  }
  vector<ii> ra(n);
  for(int i = 0; i < n; ++i) {
    int l = i, r = i;
    bs has = A[i];
    while(true) {
      int flag = 0;
      if(l and has[C[l-1]]) {
        has |= A[--l];
        ++flag;
      }
      if(r < n-1 and has[C[r]]) {
        has |= A[++r];
        ++flag;
      }
      if(!flag) break;
    }
    // cout << l+1 << ' ' << r+1 << endl;
    ra[i] = {l, r};
  }
  int q; cin >> q;
  while(q--) {
    int x, y;
    cin >> x >> y;
    --x, --y;
    cout << (ra[x].fi <= y and y <= ra[x].se ? "YES" : "NO") << endl;
  }
  return 0;
}

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