Submission #801109

#	Time	Username	Problem	Language	Result	Execution time	Memory
801109		vjudge1	Long Mansion (JOI17_long_mansion)	C++14	10 / 100	421 ms	42052 KiB

long_mansion

#include<bits/stdc++.h>
using namespace std ;
const int N = 5e5, NS = 5e3 ;
bool us[NS + 1][NS + 1] ;
int n, q, sm, c[N + 1] ;
vector<int> ks[N + 1] ;
map<int, int> ch, null ;
void bfs(int city)
{
    ch = null ;
    bool abu = 1 ;
    int l = city, r = city ;
    for(int i : ks[city])
        ch[i] = 1 ;
    us[city][city] = 1 ;
    while(abu)
    {
        abu ^= 1 ;
        if(l > 1 && ch[c[l - 1]])
        {
            l-- ;
            for(int i : ks[l])
                ch[i] = 1 ;
//            cout<<city<<' '<<l << '\n' ;
            us[city][l] = 1 ;
            abu |= 1 ;
        }
        if(r < n && ch[c[r]])
        {
            abu |= 1 ;
            r++ ;
            for(int i : ks[r])
                ch[i] = 1 ;
//            cout<<city<<' '<<r << '\n' ;
            us[city][r] = 1 ;
        }
    }
}
signed main()
{
    ios_base::sync_with_stdio( 0 ) ;
    cin.tie( 0 ) ;
    cout.tie( 0 ) ;
    cin >> n ;
    for(int i = 1 ; i < n ; i++)
        cin >> c[i] ;
    for(int i = 1 ; i <= n ; i++)
    {
        int b ;
        cin >> b ;
        sm += b ;
        for(int j = 1 ; j <= b ; j++)
        {
            int a ;
            cin >> a ;
            ks[i].push_back(a) ;
        }
    }
    if(n <= 5000 && sm <= 5000)
    {
        for(int i = 1 ; i <= n ; i++)
            bfs(i) ;
        cin >> q ;
        for(int i = 1 ; i <= q ; i++)
        {
            int x, y ;
            cin >> x >> y ;
            if(us[x][y])
                cout << "YES\n" ;
            else
                cout << "NO\n" ;
        }
        return 0 ;
    }
    return 0 ;
}

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