oj.uz

Submission #370067

# Submission time Handle Problem Language Result Execution time Memory
370067 2021-02-23T07:31:57 Z Mamnoon_Siam Long Mansion (JOI17_long_mansion) C++17
0 / 100
 3000 ms 5684 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 364 KB Output is correct
2 Correct 17 ms 492 KB Output is correct
3 Correct 33 ms 512 KB Output is correct
4 Incorrect 15 ms 492 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 364 KB Output is correct
2 Correct 17 ms 492 KB Output is correct
3 Correct 33 ms 512 KB Output is correct
4 Incorrect 15 ms 492 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2571 ms 4060 KB Output is correct
2 Execution timed out 3067 ms 5684 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 364 KB Output is correct
2 Correct 17 ms 492 KB Output is correct
3 Correct 33 ms 512 KB Output is correct
4 Incorrect 15 ms 492 KB Output isn't correct
5 Halted 0 ms 0 KB -