Submission #801932

#	Time	Username	Problem	Language	Result	Execution time	Memory
801932		vjudge1	Long Mansion (JOI17_long_mansion)	C++17	10 / 100	161 ms	26604 KiB

long_mansion

#ifdef Home
#define _GLIBCXX_DEBUG
#endif // Home

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;


const int N = 5555;

bool can[N][N];

int corr[N], have[N], T;

vector < int > V[N];

main() {
#ifdef Home
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif // Home
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, q, a, b;
    cin >> n;
    for(int i = 1; i < n; ++ i) {
        cin >> corr[i];
    }
    for(int k, i = 1; i <= n; ++ i) {
        cin >> k;
        V[i].resize(k);
        for(auto &j : V[i]) {
            cin >> j;
        }
    }
    for(int i = 1; i <= n; ++ i) {
        ++ T;
        int l = i - 1, r = i;
        for(auto &j : V[i]) {
            have[j] = T;
        }
        bool L = true, R = true;
        for(; L|R;) {
            L = R = false;
            for(; l && have[corr[l]] == T; -- l, L = true) {
                can[i][l] = true;
                for(auto &j : V[l]) {
                    have[j] = T;
                }
            }
            for(; r < n && have[corr[r]] == T; R = true) {
                ++ r;
                can[i][r] = true;
                for(auto &j : V[r]) {
                    have[j] = T;
                }
            }
        }
    }
    for(cin >> q; q --> 0;) {
        cin >> a >> b;
        cout << (can[a][b] ? "YES" : "NO") << '\n';
    }
}

Compilation message (stderr)

long_mansion.cpp:21:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   21 | main() {
      | ^~~~

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