Submission #1141145

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141145		denislav	Sprinkler (JOI22_sprinkler)	C++20	30 / 100	3186 ms	86964 KiB

sprinkler

# include <iostream>
# include <vector>
# include <queue>
using namespace std;

const int MAX=2e5+11;

int n,q;
long long bgn[MAX],MOD;
long long pw[MAX*2];
vector<int> adj[MAX];

void read()
{
    cin>>n>>MOD;
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for(int i=1;i<=n;i++) cin>>bgn[i];


    pw[0]=1;
    for(int i=1;i<=4e5;i++) pw[i]=(pw[i-1]*2)%MOD;
}

int ct;
int up[MAX];
pair<int,int> bord[MAX];
int id[MAX];

void tree_basics()
{
    for(int i=1;i<=n;i++)
    {
        bord[i]={1e9,0};
        id[i]=-1;
    }

    queue<int> q;
    q.push(1);

    while(q.size()>0)
    {
        int curr=q.front();
        q.pop();

        id[curr]=++ct;
        bord[up[curr]].first=min(bord[up[curr]].first,id[curr]);
        bord[up[curr]].second=max(bord[up[curr]].second,id[curr]);
        for(int nxt: adj[curr])
        {
            if(id[nxt]!=-1) continue;
            up[nxt]=curr;
            q.push(nxt);
        }
    }

    //for(int i=1;i<=n;i++) cout<<i<<":"<<id[i]<<"->"<<bord[i].first<<" "<<bord[i].second<<"\n";
}

long long source[41][MAX];

void update(int u, int power, long long w)
{
    while(power>=0 and u!=0)
    {
        for(int j=0;j<=power;j++) source[j][u]++;
        u=up[u];
        power--;
    }
}

void query(int u)
{
    int orig_u=u;
    int ans=source[0][u];

    int dist=1;
    int last=u;
    u=up[u];

    while(u!=0)
    {
        ans+=source[dist][u];
        if(dist==40) break;
        ans-=source[dist+1][last];

        dist++;
        last=u;
        u=up[u];
    }

    cout<<(bgn[orig_u]*pw[ans])%MOD<<"\n";
}

void solve()
{
    cin>>q;
    while(q--)
    {
        int tp;
        cin>>tp;

        if(tp==1)
        {
            int u,d,w;
            cin>>u>>d>>w;
            update(u,d,w);
        }
        else if(tp==2)
        {
            int u;
            cin>>u;
            query(u);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    read();
    tree_basics();
    solve();

    return 0;
}

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