Submission #1177505

#TimeUsernameProblemLanguageResultExecution timeMemory
1177505huypham2009Long Mansion (JOI17_long_mansion)C++20
10 / 100
3091 ms37524 KiB
#include <bits/stdc++.h>
using namespace std;
const int maxn=5e5+5;
int n,m,q,c[maxn];
bool can_visit[5005][5005];
vector<int>keys[maxn];
void xtoy(int x)
{
    set<int>s;
    s.clear();
    for(auto v:keys[x])s.insert(v);
    int i=x,j=x;
    can_visit[x][x]=1;
    while(i>1||j<n)
    {
        if(j<n&&s.find(c[j])!=s.end())
        {
            j++;
            can_visit[x][j]=1;
            for(auto v:keys[j])s.insert(v);
            continue;
        }
        if(i>1&&s.find(c[i-1])!=s.end())
        {
            i--;
            can_visit[x][i]=1;
            for(auto v:keys[i])s.insert(v);
            continue;
        }
        return;
    }
    return ;
}
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen("keys.inp","r",stdin);  freopen("keys.out","w",stdout);
    cin>>n;
    for(int i=1;i<n;i++)cin>>c[i];
    for(int i=1;i<=n;i++)
    {
        int k;
        cin>>k;
        for(int j=1;j<=k;j++)
        {
            int tmp;
            cin>>tmp;
            keys[i].push_back(tmp);
        }
    }
    for(int i=1;i<=n;i++)xtoy(i);
    cin>>q;
    while(q--)
    {
        int x,y;
        cin>>x>>y;
        if(can_visit[x][y])cout<<"YES\n";
        else cout<<"NO\n";
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...