Submission #899654

#	Time	Username	Problem	Language	Result	Execution time	Memory
899654		alexander707070	Sprinkler (JOI22_sprinkler)	C++14	9 / 100	503 ms	170132 KiB

sprinkler

#include<bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#define MAXN 200007
using namespace std;

int n,q,type;
long long mod,w;
int a,b,s,d;
vector<int> v[MAXN];
int parent[MAXN];

long long mult[MAXN][42];

void dfs(int x,int p){
    parent[x]=p;

    for(int i=0;i<v[x].size();i++){
        if(v[x][i]==p)continue;
        dfs(v[x][i],x);
    }
}

void query(int x,int dist,long long p){
    if(dist==0){
        mult[x][dist]*=p;
        mult[x][dist]%=mod;
        return;
    }

    mult[x][dist]*=p;
    mult[x][dist]%=mod;

    mult[x][dist-1]*=p;
    mult[x][dist-1]%=mod;

    if(x==0)query(parent[x],dist-2,p);
    else query(parent[x],dist-1,p);
}

long long getval(int x,int dist){
    if(dist==41)return 1;

    return (mult[x][dist]*getval(parent[x],dist+1))%mod;
}

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>mod;
    for(int i=1;i<=n-1;i++){
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    for(int i=0;i<=n;i++){
        for(int f=0;f<=40;f++){
            mult[i][f]=1;
        }
    }

    dfs(1,0);

    for(int i=1;i<=n;i++){
        cin>>mult[i][0];
    }

    cin>>q;
    for(int i=1;i<=q;i++){
        cin>>type;
        if(type==1){
            cin>>s>>d>>w;
            query(s,d,w);
        }else{
            cin>>s;
            cout<<getval(s,0)<<"\n";
        }
    }

    return 0;
}

Compilation message (stderr)

sprinkler.cpp: In function 'void dfs(int, int)':
sprinkler.cpp:18:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~

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