# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
296289 | BThero | Long Mansion (JOI17_long_mansion) | C++17 | 3036 ms | 48248 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// chrono::system_clock::now().time_since_epoch().count()
#include<bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define debug(x) cerr << #x << " = " << x << endl;
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAXN = (int)5e5 + 5;
vector<int> group[MAXN];
vector<int> keys[MAXN];
int betw[MAXN];
int A[MAXN], B[MAXN];
int L[MAXN], R[MAXN];
int n, q;
void calcB() {
B[0] = n + 1;
for (int i = 1; i <= n; ++i) {
group[i].clear();
B[i] = n + 1;
}
for (int i = 2; i <= n; ++i) {
group[betw[i - 1]].pb(i - 1);
for (int x : keys[i]) {
for (int y : group[x]) {
B[y] = i;
}
group[x].clear();
}
}
}
void calcA() {
A[n + 1] = 0;
for (int i = 1; i <= n; ++i) {
group[i].clear();
A[i] = 0;
}
for (int i = n - 1; i > 0; --i) {
group[betw[i]].pb(i + 1);
for (int x : keys[i]) {
for (int y : group[x]) {
A[y] = i;
}
group[x].clear();
}
}
}
void calcR() {
for (int i = 1; i <= n; ++i) {
R[i] = n + 1;
}
for (int r = 1; r <= n; ++r) {
// A[r + 1] < l
int l = A[r + 1] + 1;
// B[l - 1] > r
while (l <= r && B[l - 1] <= r) {
++l;
}
for (int i = l; i <= r; ++i) {
R[i] = min(R[i], r);
}
}
}
void calcL() {
for (int i = 1; i <= n; ++i) {
L[i] = 0;
}
for (int l = n; l > 0; --l) {
// B[l - 1] > r
int r = B[l - 1] - 1;
// A[r + 1] < l
while (l <= r && A[r + 1] >= l) {
--r;
}
for (int i = l; i <= r; ++i) {
L[i] = max(L[i], l);
}
}
}
void solve() {
scanf("%d", &n);
for (int i = 1; i < n; ++i) {
scanf("%d", &betw[i]);
}
for (int i = 1; i <= n; ++i) {
int sz;
scanf("%d", &sz);
keys[i].resize(sz);
for (int j = 0; j < sz; ++j) {
scanf("%d", &keys[i][j]);
}
}
calcB();
calcA();
calcR();
calcL();
scanf("%d", &q);
for (int i = 1; i <= q; ++i) {
int a, b;
scanf("%d %d", &a, &b);
// a -> b
bool ans = 1;
if (a < b) {
if (R[a] < b) {
ans = 0;
}
}
else {
if (L[a] > b) {
ans = 0;
}
}
if (ans) {
printf("YES\n");
}
else {
printf("NO\n");
}
}
}
int main() {
int tt = 1;
while (tt--) {
solve();
}
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |