oj.uz

Submission #625297

# Submission time Handle Problem Language Result Execution time Memory
625297 2022-08-09T23:29:39 Z chonka File Paths (BOI15_fil) C++17
0 / 100
 1000 ms 119092 KB 
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;

const int MAXN = 3007 ;
const int maxval = 1e6 + 7 ;

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

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

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 ;
        if ( hh <= targ ) {
            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 ) ;
    }
    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 ;
            }
        }
    }
    add ( -1 ) ;
    stk.pop_back ( ) ;
}

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 24020 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1091 ms 119092 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 24020 KB Output isn't correct
2 Halted 0 ms 0 KB -