제출 #296289

#제출 시각아이디문제언어결과실행 시간메모리
296289BTheroLong Mansion (JOI17_long_mansion)C++17
25 / 100
3036 ms48248 KiB
// 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) 메시지

long_mansion.cpp: In function 'void solve()':
long_mansion.cpp:109:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  109 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
long_mansion.cpp:112:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  112 |     scanf("%d", &betw[i]);
      |     ~~~~~^~~~~~~~~~~~~~~~
long_mansion.cpp:117:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  117 |     scanf("%d", &sz);
      |     ~~~~~^~~~~~~~~~~
long_mansion.cpp:121:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  121 |       scanf("%d", &keys[i][j]);
      |       ~~~~~^~~~~~~~~~~~~~~~~~~
long_mansion.cpp:130:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  130 |   scanf("%d", &q);
      |   ~~~~~^~~~~~~~~~
long_mansion.cpp:134:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  134 |     scanf("%d %d", &a, &b);
      |     ~~~~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...