Submission #545675

#	Time	Username	Problem	Language	Result	Execution time	Memory
545675		leaked	Sprinkler (JOI22_sprinkler)	C++14	100 / 100	674 ms	53924 KiB

sprinkler

#include <bits/stdc++.h>

#define f first
#define s second
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define vec vector
#define pb push_back
#define sz(x) (int)(x).size()
#define pw(x) (1LL<<(x))
#define fast_prep ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef long double ld;
typedef pair<int,ll> pil;
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
int M;
const int N=2e5+41;
int par[N];
int mt[N][42];
vec<int> g[N];
int a[N];
int mult(int a,int b){
    return 1ll*a*b%M;
}
void dfs(int v,int p){
    for(auto &z : g[v]){
        if(z==p) continue;
        par[z]=v;
        dfs(z,v);
    }
}
signed main(){
    fast_prep;
    int n;
    cin>>n>>M;
    for(int i=1;i<n;i++){
        int v,u;
        cin>>v>>u;--v;--u;
        g[v].pb(u);g[u].pb(v);
    }
    g[n].pb(0);g[0].pb(n);
    for(int i=n+1;i<n+40;i++){
        g[i].pb(i-1);g[i-1].pb(i);
    }
    n+=40;
    dfs(n-1,n-1);
    for(int i=0;i<n;i++)
        fill(mt[i],mt[i]+42,1);
    for(int i=0;i<n-40;i++) cin>>a[i];
    int q;
    cin>>q;
    while(q--){
        int type;
        cin>>type;
        if(type==1){
            int v,d,w;
            cin>>v>>d>>w;--v;
            while(d>=0){

//                cout<<"UPD "<<v<<' '<<d<<' '<<w<<endl;
//                cout<<"HEY "<<mt[v][d]<<' '<<mult(mt[v][d],w)<<endl;
                mt[v][d]=mult(mt[v][d],w);

                --d;v=par[v];
            }
        }
        else{
            int v;
            cin>>v;--v;
            int ans=a[v];
            for(int i=0;i<=40;i++){
                ans=mult(ans,mt[v][i]);
                ans=mult(ans,mt[v][i+1]);
                v=par[v];
            }
            cout<<ans<<'\n';
        }
    }
    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