oj.uz

Submission #890744

# Submission time Handle Problem Language Result Execution time Memory
890744 2023-12-21T21:44:01 Z Ahmed57 Sprinkler (JOI22_sprinkler) C++17
3 / 100
 1586 ms 1048576 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],q;
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;
vector<array<int,3>>Lol[200001],LOL[200001];
vector<array<int,2>>QU[200001],qu[200001];
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*4+1];
void build2(int p,int l,int r,int ty){
    if(l==r){
        seg[ty][p] = 1;
        return;
    }
    int md = (l+r)/2;
    build2(p*2,l,md,ty);
    build2(p*2+1,md+1,r,ty);
    seg[ty][p] = (seg[ty][p*2]*seg[ty][p*2+1])%L;
}
void merge(int p,int l,int r,int p1,int p2,int ty){
    if(l==r){
        seg[ty][p] = (seg[p1][p]*seg[p2][p])%L;
        return ;
    }
    int md = (l+r)/2;
    merge(p*2,l,md,p1,p2,ty);
    merge(p*2+1,md+1,r,p1,p2,ty);
    seg[ty][p] = (seg[p1][p]*seg[p2][p])%L;
}
void build(int p,int l,int r){
    if(l==r){
        build2(1,0,40,p);
        return ;
    }
    int md = (l+r)/2;
    build(p*2,l,md);build(p*2+1,md+1,r);
    merge(1,0,40,p*2,p*2+1,p);
    return ;
}
void update2(int p,int l,int r,int idx,int val,int ty){
    if(l==r){
        seg[ty][p]*=val;seg[ty][p]%=L;
        //cout<<seg[ty][p]<<endl;
        return ;
    }
    int md = (l+r)/2;
    if(idx<=md)update2(p*2,l,md,idx,val,ty);
    else update2(p*2+1,md+1,r,idx,val,ty);
    seg[ty][p] = (seg[ty][p*2]*seg[ty][p*2+1])%L;
}
void update(int p,int l,int r,int idx,int val,int ty){
    if(l==r){
        update2(1,0,40,ty,val,p);
        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);
    merge(1,0,40,p*2,p*2+1,p);
}void set2(int p,int l,int r,int idx,int ty){
    if(l==r){
        seg[ty][p] = 1;seg[ty][p]%=L;
        return ;
    }
    int md = (l+r)/2;
    if(idx<=md)set2(p*2,l,md,idx,ty);
    else set2(p*2+1,md+1,r,idx,ty);
    seg[ty][p] = (seg[ty][p*2]*seg[ty][p*2+1])%L;
}
void sett(int p,int l,int r,int idx,int ty){
    if(l==r){
        set2(1,0,40,ty,p);
        return;
    }
    int md = (l+r)/2;
    if(idx<=md)sett(p*2,l,md,idx,ty);
    else sett(p*2+1,md+1,r,idx,ty);
    merge(1,0,40,p*2,p*2+1,p);
}
int query2(int p,int l,int r,int lq,int rq,int ty){
    if(l>=lq&&r<=rq){
        return seg[ty][p];
        //cout<<seg[ty][p]<<endl;
        assert(seg[ty][p]);
    }
    if(r<lq||l>rq){
        //cout<<1<<endl;
        return 1;
    }
    int md = (l+r)/2;
    return (query2(p*2,l,md,lq,rq,ty)*query2(p*2+1,md+1,r,lq,rq,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 query2(1,0,40,ty,40,p);
    }
    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;
}
long long ANS[400001];
void comp(int i){
    int cen = getCen(i,i,dfs(i,i));
    vis[cen] = 1;
    for(auto j:LOL[cen]){
        update(1,1,q,j[0],j[2],j[1]);
        //cout<<"hh"<<endl;
    }
    for(auto j:adj[cen]){
        if(vis[j])continue;
        for(auto e:qu[getIndex[{cen,j}]]){
            ANS[e[0]]*=query(1,1,q,1,e[0],e[1]);
            ANS[e[0]]%=L;
            //cout<<query(1,1,q,1,e[0],e[1])<<"hhhh"<<endl;
        }
        for(auto e:Lol[getIndex[{cen,j}]]){
            update(1,1,q,e[0],e[2],e[1]);
            //cout<<"hh"<<endl;
        }
    }
    for(auto e:QU[cen]){
        ANS[e[0]]*=query(1,1,q,1,e[0],e[1]);
        ANS[e[0]]%=L;
    }
    for(auto j:LOL[cen]){
        sett(1,1,q,j[0],j[1]);
    }
    for(auto j:adj[cen]){
        if(vis[j])continue;
        for(auto e:Lol[getIndex[{cen,j}]]){
            sett(1,1,q,e[0],e[1]);
        }
    }
    reverse(adj[cen].begin(),adj[cen].end());
    for(auto j:adj[cen]){
        if(vis[j])continue;
        for(auto e:qu[getIndex[{cen,j}]]){
            ANS[e[0]]*=query(1,1,q,1,e[0],e[1]);
            ANS[e[0]]%=L;
        }
        for(auto e:Lol[getIndex[{cen,j}]]){
            update(1,1,q,e[0],e[2],e[1]);
        }
    }for(auto j:adj[cen]){
        if(vis[j])continue;
        for(auto e:Lol[getIndex[{cen,j}]]){
            sett(1,1,q,e[0],e[1]);
        }
    }
    reverse(adj[cen].begin(),adj[cen].end());
    for(auto j:adj[cen]){
        if(vis[j])continue;
        comp(j);
    }
}
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;
    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;
    cin>>q;
    build(1,1,q);
    //cout<<seg[1][1]<<endl;
    vector<int> lw;
    for(int Q = 1;Q<=q;Q++){
        int ty;cin>>ty;
        if(ty==1){
            int x,d,v;
            cin>>x>>d>>v;
            int org = x;
            LOL[x].push_back({Q,d,v});
            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){
                    Lol[id].push_back({Q,d-le,v});
                }
            }
        }else{
            lw.push_back(Q);
            int x;cin>>x;
            ANS[Q] = h[x];
            QU[x].push_back({Q,0});
            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);
                qu[id].push_back({Q,le});
                //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<<"hhh"<<endl;
    for(int i = 1;i<=n;i++)vis[i] =0;
    comp(1);
    sort(lw.begin(),lw.end());
    //cout<<"***********************"<<endl;
    for(auto i:lw){
        cout<<ANS[i]<<endl;
    }
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 47452 KB Output is correct
2 Correct 8 ms 47452 KB Output is correct
3 Correct 9 ms 47536 KB Output is correct
4 Correct 55 ms 52572 KB Output is correct
5 Correct 60 ms 52504 KB Output is correct
6 Correct 56 ms 52316 KB Output is correct
7 Correct 54 ms 52316 KB Output is correct
8 Correct 26 ms 52056 KB Output is correct
9 Correct 17 ms 49752 KB Output is correct
10 Correct 18 ms 49752 KB Output is correct
11 Correct 20 ms 49756 KB Output is correct
12 Correct 19 ms 49756 KB Output is correct
13 Correct 19 ms 49756 KB Output is correct
14 Correct 17 ms 49812 KB Output is correct
15 Correct 21 ms 49752 KB Output is correct
16 Correct 21 ms 49752 KB Output is correct
17 Correct 22 ms 49856 KB Output is correct
18 Correct 21 ms 49756 KB Output is correct
19 Correct 18 ms 50072 KB Output is correct
20 Correct 22 ms 49832 KB Output is correct
21 Correct 21 ms 49752 KB Output is correct
22 Correct 23 ms 49756 KB Output is correct
23 Correct 21 ms 49852 KB Output is correct
24 Correct 17 ms 49756 KB Output is correct
25 Correct 21 ms 49756 KB Output is correct
26 Correct 22 ms 49748 KB Output is correct
27 Correct 23 ms 49756 KB Output is correct
28 Correct 21 ms 49664 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 47452 KB Output is correct
2 Runtime error 1300 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 47452 KB Output is correct
2 Runtime error 1300 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 47452 KB Output is correct
2 Runtime error 1586 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 47448 KB Output is correct
2 Runtime error 1574 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 47452 KB Output is correct
2 Correct 8 ms 47452 KB Output is correct
3 Correct 9 ms 47536 KB Output is correct
4 Correct 55 ms 52572 KB Output is correct
5 Correct 60 ms 52504 KB Output is correct
6 Correct 56 ms 52316 KB Output is correct
7 Correct 54 ms 52316 KB Output is correct
8 Correct 26 ms 52056 KB Output is correct
9 Correct 17 ms 49752 KB Output is correct
10 Correct 18 ms 49752 KB Output is correct
11 Correct 20 ms 49756 KB Output is correct
12 Correct 19 ms 49756 KB Output is correct
13 Correct 19 ms 49756 KB Output is correct
14 Correct 17 ms 49812 KB Output is correct
15 Correct 21 ms 49752 KB Output is correct
16 Correct 21 ms 49752 KB Output is correct
17 Correct 22 ms 49856 KB Output is correct
18 Correct 21 ms 49756 KB Output is correct
19 Correct 18 ms 50072 KB Output is correct
20 Correct 22 ms 49832 KB Output is correct
21 Correct 21 ms 49752 KB Output is correct
22 Correct 23 ms 49756 KB Output is correct
23 Correct 21 ms 49852 KB Output is correct
24 Correct 17 ms 49756 KB Output is correct
25 Correct 21 ms 49756 KB Output is correct
26 Correct 22 ms 49748 KB Output is correct
27 Correct 23 ms 49756 KB Output is correct
28 Correct 21 ms 49664 KB Output is correct
29 Correct 9 ms 47452 KB Output is correct
30 Runtime error 1300 ms 1048576 KB Execution killed with signal 9
31 Halted 0 ms 0 KB -