Submission #1023824

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023824		manizare	Sprinkler (JOI22_sprinkler)	C++14	100 / 100	594 ms	105556 KiB

sprinkler

#include <bits/stdc++.h>
 
 
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second 
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define PII pair<pii , pii>
#define ld long double 
#define int long long 
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= b;i++)
#define per(i, a , b) for(int i=a;i >= b;i--)
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 2e5 + 10  , sq = 550,  inf = 1e8+10 , mod = 10007 , lg = 20  ;
int n , l , h[maxn]  , dis[maxn] , par[maxn] ;
vector <int> G[maxn] ;

void dfs(int v){
    for(int u : G[v]){
        if(par[v] == u)continue ; 
        dis[u] = dis[v] +1  ;
        par[u] = v ; 
        dfs(u) ;
    }
}
int t[maxn][45] , ted[maxn+100] ;

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);    
    cin >> n >> l ; 
    rep(i , 1, n-1){
        int v , u ;cin >> v >> u ; 
        G[v].pb(u) ;
        G[u].pb(v) ;
    }
    rep(i ,1 , n)cin >> h[i] ; 
    int q ;cin >> q ;rep(i ,0, n+42)ted[i] = 1 ;
    rep(i , 1 , n)rep(j , 0 , 40)t[i][j] = 1 ;
    dfs(1) ;
    while(q--){
        int T ;
        cin >> T ; 
        if(T == 1){
            int x , w , d ;
            cin >> x >> d >> w ; 
            if(d >= dis[x])ted[d-dis[x]]  = ted[d-dis[x]] * w % l ;
            while(d >= 0){
                if(x == 1)break ; 
                t[x][d] = (t[x][d] * w % l); 
                if(d)t[x][d-1] = t[x][d-1] * w % l  ;
                d--;
                x = par[x] ;               
            }      
        }else{
            int x ;cin >> x ; 
            int d = 0 ;
            int ans = h[x]  ;
            rep(j , dis[x] , 42)ans= ans * ted[j]% l ; 
            while(x!=1){
                if(d > 40)break ;
                ans= ans * t[x][d] % l ; 
                d++ ;      
                x = par[x] ;
            } 
            cout << ans << "\n" ; 
        }      
    }  
}
/*
*/

• Subtask 1: 3 / 3
• Subtask 2: 9 / 9
• Subtask 3: 29 / 29
• Subtask 4: 12 / 12
• Subtask 5: 30 / 30
• Subtask 6: 17 / 17