oj.uz

Submission #573312

# Submission time Handle Problem Language Result Execution time Memory
573312 2022-06-06T11:56:50 Z chonka Sprinkler (JOI22_sprinkler) C++
0 / 100
 403 ms 78556 KB 
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
const int MAXN = 200047 ;
const int MXVAL = 43 ;

int n , MOD ;
int prv[ MAXN ] ;
ll coef[ MAXN ][ MXVAL ] ;
ll h[ MAXN ] ;


void input ( ) {
    cin >> n >> MOD ;
    for ( int i = 1 ; i < n ; ++ i ) {
        int x , y ; cin >> x >> y ;
        prv[ y ] = x ;
    }
    for ( int i = 1 ; i <= n ; ++ i ) {
        cin >> h[ i ] ;
        for ( int j = 0 ; j < MXVAL ; ++ j ) {
            coef[ i ][ j ] = 1 ;
        }
    }
    prv[ 1 ] = n + 1 ;
    for ( int i = n + 1 ; i <= n + MXVAL ; ++ i ) {
        prv[ i ] = i + 1 ;
        for ( int j = 0 ; j < MXVAL ; ++ j ) {
            coef[ i ][ j ] = 1 ;
        }
    }
}

void solve ( ) {
    int q ; cin >> q ;
    while ( q -- ) {
        int type ;
        cin >> type ;
        if ( type == 1 ) {
            int x , dist , nw ;
            cin >> x >> dist >> nw ;
            int y = x ;
            for ( int i = 0 ; i <= dist ; ++ i ) {
                coef[ y ][ dist - i ] = ( coef[ y ][ dist - i ] * nw ) % MOD ;
                y = prv[ y ] ;
            }
        }
        else {
            int x ;
            cin >> x ;
            ll ans = 1 ;
            int y = x ;
            for ( int i = 0 ; i <= 40 ; ++ i ) {
                ans = ( ans * coef[ y ][ i ] ) % MOD ;
                ans = ( ans * coef[ y ][ i + 1 ] ) % MOD ;
                y = prv[ y ] ;
            }
            cout << ( h[ x ] * ans ) % MOD << "\n" ;
        }
    }
}

int main ( ) {
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    int t ;
    t = 1 ;
    /// scanf ( "%d" , &t ) ;
    /// cin >> t ;
    while ( t -- ) {
        input ( ) ;
        solve ( ) ;
    }
    return 0 ;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 0 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 12.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 403 ms 78556 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 0 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -