Submission #282464

#	Time	Username	Problem	Language	Result	Execution time	Memory
282464		rama_pang	Long Mansion (JOI17_long_mansion)	C++14	100 / 100	441 ms	52708 KiB

long_mansion

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

const int MAXN = 5e5 + 5;

class DisjointSet {
 public:
  int n;
  vector<int> p;
  DisjointSet() {}
  DisjointSet(int n) : n(n), p(n) {
    iota(begin(p), end(p), 0);
  }
  int Find(int x) {
    return p[x] == x ? x : p[x] = Find(p[x]);
  }
  int Unite(int x, int y) {
    x = Find(x), y = Find(y);
    if (x != y) {
      p[x] = y;
      return 1;
    }
    return 0;
  }
};

int N;
int C[MAXN];
vector<int> keys[MAXN];

int vis[MAXN];
DisjointSet D(MAXN);
pair<int, int> memo[MAXN];

bool Unlock(int l, int r, int type) {
  return *lower_bound(begin(keys[type]), end(keys[type]), l) <= r;
}

array<int, 3> Dp(int st) {
  if (vis[st]) {
    return {st, st, st};
  }
  if (D.Find(st) != st) {
    return Dp(D.Find(st));
  }
  if (memo[st].first != -1) {
    return {-1, memo[st].first, memo[st].second};
  }
  vis[st] = 1;
  int l = st, r = st;
  while (true) {
    if (l > 0 && Unlock(l, r, C[l - 1])) {
      auto nxt = Dp(l - 1);
      l = min(l, nxt[1]), r = max(r, nxt[2]);
      if (nxt[0] != -1 && D.Unite(st, nxt[0])) { // found cycle, we merge the intervals
        vis[st] = 0;
        return {nxt[0], l, r};
      }
    } else if (r + 1 < N && Unlock(l, r, C[r])) {
      auto nxt = Dp(r + 1);
      l = min(l, nxt[1]), r = max(r, nxt[2]);
      if (nxt[0] != -1 && D.Unite(st, nxt[0])) { // found cycle, we merge the intervals
        vis[st] = 0;
        return {nxt[0], l, r};
      }
    } else {
      break;
    }
  }
  vis[st] = 0;
  memo[st] = {l, r};
  return {-1, l, r};
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  cin >> N;
  for (int i = 0; i + 1 < N; i++) {
    cin >> C[i];
    C[i] -= 1;
  }
  for (int i = 0; i < N; i++) {
    memo[i] = {-1, -1};
    int k;
    cin >> k;
    while (k--) {
      int key;
      cin >> key;
      key--;
      keys[key].emplace_back(i);
    }
  }
  for (int i = 0; i < N; i++) {
    keys[i].emplace_back(N);
  }
  int Q;
  cin >> Q;
  for (int i = 0; i < Q; i++) {
    int x, y;
    cin >> x >> y;
    x--, y--;
    auto ans = Dp(x);
    if (ans[1] <= y && y <= ans[2]) {
      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