Submission #447601

#	Time	Username	Problem	Language	Result	Execution time	Memory
447601		blue	Long Mansion (JOI17_long_mansion)	C++17	10 / 100	3076 ms	26948 KiB

long_mansion

#include <iostream>
#include <set>
#include <vector>
using namespace std;

int main()
{
    int N;
    cin >> N;

    int C[N+1];
    for(int i = 1; i < N; i++) cin >> C[i];

    set<int> keys[N+1];
    for(int i = 1; i <= N; i++)
    {
        int B;
        cin >> B;

        for(int j = 1; j <= B; j++)
        {
            int A;
            cin >> A;
            keys[i].insert(A);
        }
    }


    vector<int> left_reach(1+N), right_reach(1+N);

    for(int i = 1; i <= N; i++)
    {
        left_reach[i] = right_reach[i] = i;
        set<int> curr_keys;
        for(int k: keys[i]) curr_keys.insert(k);

        while(1)
        {
            if(left_reach[i] != 1 && curr_keys.find( C[ left_reach[i]-1 ]) != curr_keys.end() )
            {
                left_reach[i]--;
                for(int k: keys[ left_reach[i] ]) curr_keys.insert(k);
            }
            else if(right_reach[i] != N && curr_keys.find( C[ right_reach[i] ] ) != curr_keys.end())
            {
                right_reach[i]++;
                for(int k: keys[ right_reach[i] ]) curr_keys.insert(k);
            }
            else break;
        }
    }



    int Q;
    cin >> Q;
    for(int q = 1; q <= Q; q++)
    {
        int x, y;

        cin >> x >> y;

        if(left_reach[x] <= y && y <= right_reach[x])
        {
            cout << "YES\n";
        }
        else cout << "NO\n";
    }
}

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