Submission #573323

#	Time	Username	Problem	Language	Result	Execution time	Memory
573323		chonka	Sprinkler (JOI22_sprinkler)	C++98	100 / 100	644 ms	97520 KiB

sprinkler

#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
const int MAXN = 200047 ;
const int MXVAL = 43 ;

int n , MOD ;
vector < int > v[ MAXN ] ;
int prv[ MAXN ] ;
ll coef[ MAXN ][ MXVAL ] ;
ll h[ MAXN ] ;

void dfs ( int x , int aux ) {
    for ( auto y : v[ x ] ) {
        if ( y == aux ) { continue ; }
        prv[ y ] = x ;
        dfs ( y , x ) ;
    }
}

void input ( ) {
    cin >> n >> MOD ;
    for ( int i = 1 ; i < n ; ++ i ) {
        int x , y ; cin >> x >> y ;
        v[ x ].push_back ( y ) ;
        v[ y ].push_back ( x ) ;
    }
    dfs ( 1 , -1 ) ;
    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: 3 / 3
• Subtask 2: 9 / 9
• Subtask 3: 29 / 29
• Subtask 4: 12 / 12
• Subtask 5: 30 / 30
• Subtask 6: 17 / 17