oj.uz

Submission #721147

# Submission time Handle Problem Language Result Execution time Memory
721147 2023-04-10T11:28:31 Z lam Sprinkler (JOI22_sprinkler) C++14
42 / 100
 1674 ms 232220 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Incorrect 7 ms 14432 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 14428 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 14428 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14436 KB Output is correct
2 Correct 1654 ms 230220 KB Output is correct
3 Correct 1519 ms 228156 KB Output is correct
4 Correct 1520 ms 227980 KB Output is correct
5 Correct 1234 ms 210352 KB Output is correct
6 Correct 1116 ms 209584 KB Output is correct
7 Correct 1012 ms 207976 KB Output is correct
8 Correct 558 ms 193024 KB Output is correct
9 Correct 1571 ms 226784 KB Output is correct
10 Correct 1552 ms 229724 KB Output is correct
11 Correct 1314 ms 210220 KB Output is correct
12 Correct 1245 ms 211332 KB Output is correct
13 Correct 827 ms 204132 KB Output is correct
14 Correct 863 ms 208960 KB Output is correct
15 Correct 8 ms 14420 KB Output is correct
16 Correct 8 ms 14420 KB Output is correct
17 Correct 8 ms 14420 KB Output is correct
18 Correct 8 ms 14436 KB Output is correct
19 Correct 8 ms 14420 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 1573 ms 228900 KB Output is correct
3 Correct 1674 ms 225600 KB Output is correct
4 Correct 1610 ms 227268 KB Output is correct
5 Correct 1287 ms 212060 KB Output is correct
6 Correct 1179 ms 211988 KB Output is correct
7 Correct 1077 ms 210796 KB Output is correct
8 Correct 574 ms 192640 KB Output is correct
9 Correct 1588 ms 232220 KB Output is correct
10 Correct 1541 ms 230664 KB Output is correct
11 Correct 1301 ms 212836 KB Output is correct
12 Correct 1220 ms 211312 KB Output is correct
13 Correct 819 ms 204200 KB Output is correct
14 Correct 861 ms 209320 KB Output is correct
15 Correct 7 ms 14420 KB Output is correct
16 Correct 8 ms 14420 KB Output is correct
17 Correct 9 ms 14420 KB Output is correct
18 Correct 8 ms 14420 KB Output is correct
19 Correct 8 ms 14432 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Incorrect 7 ms 14432 KB Output isn't correct
3 Halted 0 ms 0 KB -