oj.uz

Submission #625391

# Submission time Handle Problem Language Result Execution time Memory
625391 2022-08-10T10:14:55 Z chonka File Paths (BOI15_fil) C++17
0 / 100
 1000 ms 136840 KB 
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;

const int MAXN = 3007 ;
const int maxval = 2e6 + 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[ 2 * maxval ] ;
vector < int > stk ;
int dep[ MAXN ] ;
vector < int > divs[ maxval ] ;

void add ( int coef ) {
    int x = stk.back ( ) ;
    for ( int i = 1 ; i <= n ; ++ i ) { 
        int w = dep[ i ] + skiplen + 1 - dep[ stk.back ( ) ] ;
        drop[ maxval + w ] += coef ;
    }
}

void add_subtree ( int x , int root , int coef ) {
    int hh = dep[ x ] - dep[ root ] + skiplen + 1 ;
    if ( hh <= targ ) {
        per[ hh ] += coef ;
    }
    for ( auto y : v[ x ] ) {
        add_subtree ( y , root , coef ) ;
    }
}


void init ( int x ) {
    if ( dep[ x ] + skiplen <= targ ) {
        ++ per[ dep[ x ] + skiplen ] ;
    }
    for ( auto y : v[ x ] ) {
        dep[ y ] = dep[ x ] + a[ y ] + 1 ;
        init ( y ) ;
    }
}

void dfs ( int x ) {
    stk.push_back ( x ) ;
    add ( 1 ) ;
    add_subtree ( x , x , 1 ) ;
    for ( auto y : v[ x ] ) {
        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 ;
                }
            }
        }
        if ( drop[ maxval + tot - targ ] > 0 ) {
            ans[ id ] = true ;
        }
    }
    add_subtree ( x , x , -1 ) ;
    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 ;
    init ( 0 ) ;
    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 ;
}

Compilation message

fil.cpp: In function 'void add(int)':
fil.cpp:20:9: warning: unused variable 'x' [-Wunused-variable]
   20 |     int x = stk.back ( ) ;
      |         ^

Subtask #1
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 47444 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 1084 ms 136840 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

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