oj.uz

Submission #890718

# Submission time Handle Problem Language Result Execution time Memory
890718 2023-12-21T19:19:35 Z Ahmed57 Sprinkler (JOI22_sprinkler) C++17
3 / 100
 4000 ms 619304 KB 
#include <bits/stdc++.h>

using namespace std;
#define int long long
int dp[200001][41];
int lo[200001][41];
int P[200001],dep[200001];
int Pr[200001][41];
int cnt = 1,n,L;
map<int,int> mp[200001];
vector<int> adj[200001];
int h[200001],sz[200001];
int vis[200001],ma[200001],mi[200001];
map<pair<int,int>,int> getIndex;
int dfs(int i,int pr){
    sz[i] = 1;
    for(auto j:adj[i]){
        if(j==pr||vis[j])continue;
        sz[i]+=dfs(j,i);
    }
    return sz[i];
}
int getCen(int i,int pr,int ss){
    for(auto j:adj[i]){
        if(j==pr||vis[j])continue;
        if(sz[j]*2>ss)return getCen(j,i,ss);
    }
    return i;
}
void lol(int i,int pr,int co,int de){
    mp[de][i] = co;
    for(auto j:adj[i]){
        if(j==pr||vis[j])continue;
        lol(j,i,co,de);
    }
}
void centroid(int i,int pr){
    int cen = getCen(i,i,dfs(i,i));
    vis[cen] = 1;
    P[cen] = pr;
    mi[cen] =cnt;
    for(auto j:adj[cen]){
        if(vis[j])continue;
        lol(j,cen,j,cen);
        getIndex[{cen,j}] = cnt++;
    }
    ma[cen] = cnt-1;
    for(auto j:adj[cen]){
        if(vis[j])continue;
        centroid(j,cen);
    }
}
void init(int i,int pr){
    Pr[i][0] = pr;
    dep[i] = dep[pr]+1;
    for(int j = 1;j<19;j++){
        Pr[i][j] = Pr[Pr[i][j-1]][j-1];
    }
    for(auto j:adj[i]){
        if(j==pr)continue;
        init(j,i);
    }
}
int lca(int a,int b){
    int sum = dep[a]+dep[b];
    if(dep[a]<dep[b])swap(a,b);
    for(int j = 18;j>=0;j--){
        if(dep[Pr[a][j]]>=dep[b])a = Pr[a][j];
    } 
    if(a==b){
        return sum-2*dep[a];
    }
    for(int j = 18;j>=0;j--){
        if(Pr[a][j]!=Pr[b][j]){
            a = Pr[a][j];
            b = Pr[b][j];
        }
    }
    return sum-2*dep[Pr[a][0]];
}
int seg[800001][41];
void build(int p,int l,int r){
    if(l==r){
        for(int j = 0;j<=40;j++){
            seg[p][j] = 1;
        }
        return ;
    }
    int md = (l+r)/2;
    build(p*2,l,md);build(p*2+1,md+1,r);
    for(int j = 0;j<=40;j++){
        seg[p][j] = seg[p*2][j]*seg[p*2+1][j];
    }
    return ;
}
void update(int p,int l,int r,int idx,int val,int ty){
    if(l==r){
        seg[p][ty]*=val;seg[p][ty]%=L;return ;
    }
    int md = (l+r)/2;
    if(idx<=md)update(p*2,l,md,idx,val,ty);
    else update(p*2+1,md+1,r,idx,val,ty);
    seg[p][ty] = (seg[p*2][ty]*seg[p*2+1][ty])%L;
}
int query(int p,int l,int r,int lq,int rq,int ty){
    if(r<lq||l>rq||lq>rq)return 1;
    if(l>=lq&&r<=rq){
        return seg[p][ty];
    }
    int md = (l+r)/2;
    return (query(p*2,l,md,lq,rq,ty)*query(p*2+1,md+1,r,lq,rq,ty))%L;
}
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    //freopen("input.txt","r",stdin);
    //freopen("outout.txt","w",stdout);
    cin>>n>>L;
    for(int i = 0;i<n-1;i++){
        int a,b;cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for(int i = 1;i<=n;i++){
        cin>>h[i];
    }
    //cout<<"hhh"<<endl;
    init(1,1);
    //cout<<"hhh"<<endl;
    build(1,1,n);
    centroid(1,-1);
    //cout<<cnt<<endl;
    for(int i = 1;i<=n;i++){
        for(int j = 0;j<=40;j++)dp[i][j] = 1;
        if(i<=cnt){
            for(int j = 0;j<=40;j++)lo[i-1][j] = 1;
        }
    }
    //cout<<"hhh"<<endl;
    int q;cin>>q;
    while(q--){
        int ty;cin>>ty;
        if(ty==1){
            int x,d,v;
            cin>>x>>d>>v;
            int org = x;
            for(int j = 0;j<=d;j++){dp[x][j]*=v;dp[x][j]%=L;}
            while(P[x]!=-1){
                x = P[x];
                int w = mp[x][org];
                int id = getIndex[{x,w}];
                //cout<<x<<"x"<<q<<" "<<id<<endl;
                int le = lca(x,org);
                if(le<=d){
                    for(int j = 0;j<=d-le;j++){
                        update(1,1,n,id,v,j);
                    }
                }
            }
        }else{
            int x;cin>>x;
            long long all = (h[x]*(mi[x]==0?1:query(1,1,n,mi[x],ma[x],0)))%L;
            all*=dp[x][0];all%=L;
            //cout<<all<<"pp"<<endl;
            int org = x;
            while(P[x]!=-1){
                x = P[x];
                int w = mp[x][org];
                int id = getIndex[{x,w}];
                //cout<<x<<"hhh "<<id<<endl;
                int le = lca(x,org);
                if(le<=40){all*=query(1,1,n,mi[x],id-1,le);all%=L;}
                if(le<=40){all*=query(1,1,n,id+1,ma[x],le);all%=L;}
                if(le<=40){all*=dp[x][le];all%=L;}
                //cout<<ma[x]<<endl;
                //cout<<dp[x][le]<<" "<<query(1,1,n,mi[x],id-1,le)<<" "<<query(1,1,n,id+1,ma[x],le)<<endl;
            }
            cout<<all<<endl;
        }
    }
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24924 KB Output is correct
2 Correct 5 ms 24924 KB Output is correct
3 Correct 5 ms 24924 KB Output is correct
4 Correct 15 ms 27992 KB Output is correct
5 Correct 14 ms 27740 KB Output is correct
6 Correct 13 ms 27740 KB Output is correct
7 Correct 13 ms 27740 KB Output is correct
8 Correct 9 ms 27484 KB Output is correct
9 Correct 6 ms 24924 KB Output is correct
10 Correct 5 ms 24924 KB Output is correct
11 Correct 5 ms 24920 KB Output is correct
12 Correct 5 ms 25008 KB Output is correct
13 Correct 5 ms 24924 KB Output is correct
14 Correct 5 ms 24924 KB Output is correct
15 Correct 5 ms 24924 KB Output is correct
16 Correct 6 ms 25084 KB Output is correct
17 Correct 6 ms 24924 KB Output is correct
18 Correct 6 ms 24920 KB Output is correct
19 Correct 5 ms 24924 KB Output is correct
20 Correct 5 ms 24924 KB Output is correct
21 Correct 5 ms 24924 KB Output is correct
22 Correct 5 ms 24924 KB Output is correct
23 Correct 5 ms 24924 KB Output is correct
24 Correct 5 ms 24972 KB Output is correct
25 Correct 5 ms 25120 KB Output is correct
26 Correct 5 ms 24924 KB Output is correct
27 Correct 5 ms 24924 KB Output is correct
28 Correct 7 ms 24920 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24924 KB Output is correct
2 Execution timed out 4093 ms 560852 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24924 KB Output is correct
2 Execution timed out 4093 ms 560852 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 24924 KB Output is correct
2 Execution timed out 4078 ms 619304 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 24924 KB Output is correct
2 Execution timed out 4085 ms 617548 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24924 KB Output is correct
2 Correct 5 ms 24924 KB Output is correct
3 Correct 5 ms 24924 KB Output is correct
4 Correct 15 ms 27992 KB Output is correct
5 Correct 14 ms 27740 KB Output is correct
6 Correct 13 ms 27740 KB Output is correct
7 Correct 13 ms 27740 KB Output is correct
8 Correct 9 ms 27484 KB Output is correct
9 Correct 6 ms 24924 KB Output is correct
10 Correct 5 ms 24924 KB Output is correct
11 Correct 5 ms 24920 KB Output is correct
12 Correct 5 ms 25008 KB Output is correct
13 Correct 5 ms 24924 KB Output is correct
14 Correct 5 ms 24924 KB Output is correct
15 Correct 5 ms 24924 KB Output is correct
16 Correct 6 ms 25084 KB Output is correct
17 Correct 6 ms 24924 KB Output is correct
18 Correct 6 ms 24920 KB Output is correct
19 Correct 5 ms 24924 KB Output is correct
20 Correct 5 ms 24924 KB Output is correct
21 Correct 5 ms 24924 KB Output is correct
22 Correct 5 ms 24924 KB Output is correct
23 Correct 5 ms 24924 KB Output is correct
24 Correct 5 ms 24972 KB Output is correct
25 Correct 5 ms 25120 KB Output is correct
26 Correct 5 ms 24924 KB Output is correct
27 Correct 5 ms 24924 KB Output is correct
28 Correct 7 ms 24920 KB Output is correct
29 Correct 5 ms 24924 KB Output is correct
30 Execution timed out 4093 ms 560852 KB Time limit exceeded
31 Halted 0 ms 0 KB -