제출 #721147

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
721147		lam	Sprinkler (JOI22_sprinkler)	C++14	42 / 100	1674 ms	232220 KiB

sprinkler

#include <bits/stdc++.h>
#define int long long
using namespace std;

struct fen
{
    int n;
    int f[42];
    void reset(int sl)
    {
        fill_n(f,sl+1,0);
        n=sl;
    }
    void add(int x, int val)
    {
        while (x>0)
        {
            f[x]++;
            x-=(x&-x);
        }
    }
    int get(int x)
    {
        int temp=0;
        while (x<=n)
        {
            temp+=f[x];
            x+=(x&-x);
        }
        return temp;
    }
};
const int maxn = 2e5 + 10;
int n,mod,q,W;
int a[maxn];
int ppow(int x, int y)
{
    int temp=1LL;
    while (y)
    {
        if (y&1) temp=temp*x%mod;
        x=x*x%mod;
        y/=2;
    }
    return temp;
}
vector <fen> freq[maxn];
fen freqs[maxn];
vector <int> adj[maxn],depth[maxn];
int s[maxn],par[maxn],cid[maxn];
bool dau[maxn];
int get_sz(int x, int p)
{
    s[x]=1;
    for (int i:adj[x])
        if (i!=p&&!dau[i]) s[x]+=get_sz(i,x);
    return s[x];
}

int find_centroid(int x, int p, int sz)
{
    for (int i:adj[x])
        if (i!=p&&!dau[i]&&2*s[i]>sz) return find_centroid(i,x,sz);
    return x;
}

void dfs(int x, int p, int dep)
{
    depth[x].push_back(dep);
    for (int i:adj[x])
        if (i!=p&&!dau[i]) dfs(i,x,dep+1);
}

void decompose(int x, int p, int id)
{
    x=find_centroid(x,x,get_sz(x,x));
    par[x]=p;
    dau[x]=1;
    depth[x].push_back(0);
    cid[x]=id;
    int cnt=0;
    for (int i:adj[x])
        if (!dau[i])
    {
        dfs(i,x,1);
        freq[x].emplace_back();
        freq[x].back().reset(41);
        decompose(i,x,cnt);
        cnt++;
    }
    freqs[x].reset(41);
}

void update(int x, int D, int w)
{
    int p=x; int id=-1;
    for (int i=depth[x].size()-1; i>=0; i--)
    {
        int d = depth[x][i];
        if (d<=D)
        {
            freqs[p].add(D-d+1,1);
            if (id!=-1) freq[p][id].add(D-d+1,1);
        }
        id=cid[p];
        p=par[p];
    }
}

int get(int x)
{
    int p=x; int id=-1;
    int cnt=0;
    for (int i=depth[x].size()-1; i>=0; i--)
    {
        int d = depth[x][i];
        if (d<=40)
        {
            cnt+=freqs[p].get(d+1);
            if (id!=-1) cnt-=freq[p][id].get(d+1);
        }
        id=cid[p];
        p=par[p];
    }
    return cnt;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    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>>a[i];
    decompose(1,-1,-1);
    cin>>q;
    for (int i=1; i<=q; i++)
    {
        int t; cin>>t;
        if (t==1)
        {
            int x,d,w; cin>>x>>d>>w;
            W=w;
            update(x,d,w);
        }
        else
        {
            int x; cin>>x;
            int cnt = get(x);
            int ans = a[x]*ppow(W,cnt)%mod;
//            cout<<x<<" : "<<cnt<<'\n';
            cout<<ans<<'\n';
        }

    }
}

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