Submission #625295

#	Time	Username	Problem	Language	Result	Execution time	Memory
625295		chonka	File Paths (BOI15_fil)	C++17	0 / 100	1098 ms	161364 KiB

fil

#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;

const int MAXN = 3007 ;

int n , q , targ , skiplen ;
int a[ MAXN ] ;
vector < int > v[ MAXN ] ;
vector < pair < int , int > > qlist[ MAXN ] ;
bool ans[ MAXN ] ;

int per[ 1000 * MAXN ] , drop[ 1000 * MAXN ] ;
vector < int > stk ;
int dep[ MAXN ] ;
vector < int > divs[ 1000 * MAXN ] ;

void add ( int coef ) {
    int sz = stk.size ( ) ;
    for ( int i = 0 ; i < sz ; ++ i ) {
        int hh = dep[ stk.back ( ) ] - dep[ stk[ i ] ] + skiplen + 1 ;
        per[ hh ] += coef ;

        int w = skiplen + 1 - ( dep[ stk.back ( ) ] - dep[ stk[ i ] ] ) ;
        if ( w >= 0 ) {
            drop[ w ] += coef ;
        }
    }
}

void dfs ( int x ) {
    stk.push_back ( x ) ;
    add ( 1 ) ;
    for ( auto y : v[ x ] ) {
        dep[ y ] = dep[ x ] + a[ y ] + 1 ;
        dfs ( y ) ;
    }
    add ( -1 ) ;
    stk.pop_back ( ) ;
    for ( auto [ len , id ] : qlist[ x ] ) {
        int tot = dep[ x ] + len ;
        if ( tot <= targ ) {
            for ( auto x : divs[ targ - tot ] ) {
                if ( per[ x ] > 0 ) {
                    ans[ id ] = true ;
                    break ;
                }
            }
        }
        else {
            if ( tot - targ <= targ && drop[ tot - targ ] > 0 ) {
                ans[ id ] = true ;
            }
        }
    }
}

void solve ( ) { 
    cin >> n >> q >> targ ;
    cin >> skiplen ;
    for ( int i = 1 , x ; i <= n ; ++ i ) {
        cin >> x >> a[ i ] ;
        v[ x ].push_back ( i ) ;
    }
    for ( int i = 1 , wh , x ; i <= q ; ++ i ) {
        cin >> wh >> x ;
        qlist[ wh ].push_back ( { x , i } ) ;
    }
    for ( int i = 1 ; i <= targ ; ++ i ) {
        for ( int j = i ; j <= targ ; j += i ) {
            divs[ j ].emplace_back ( i ) ;
        }
    }
    per[ 0 ] = drop[ 0 ] = 1 ;
    divs[ 0 ].push_back ( 0 ) ;
    dep[ 0 ] = 1 ;
    dfs ( 0 ) ;
    for ( int i = 1 ; i <= q ; ++ i ) {
        if ( ans[ i ] == true ) { cout << "YES\n" ; }
        else { cout << "NO\n" ; }
    }
}

int main ( ) {
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    int t = 1 ; // cin >> t ; 
    while ( t -- ) { solve ( ) ; }
    return 0 ;
}

• Subtask 1: 0 / 33
• Subtask 2: 0 / 33
• Subtask 3: 0 / 34