oj.uz

Submission #890747

# Submission time Handle Problem Language Result Execution time Memory
890747 2023-12-21T21:50:13 Z Ahmed57 Sprinkler (JOI22_sprinkler) C++17
3 / 100
 1570 ms 1048576 KB 
#include <bits/stdc++.h>
 
using namespace std;
#define int long long
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];
bool vis[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;
    for(auto j:adj[cen]){
        if(vis[j])continue;
        lol(j,cen,j,cen);
        getIndex[{cen,j}] = cnt++;
    }
    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[1200001][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<<"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 14 ms 43352 KB Output is correct
2 Correct 9 ms 43356 KB Output is correct
3 Correct 9 ms 43356 KB Output is correct
4 Correct 53 ms 46484 KB Output is correct
5 Correct 62 ms 46324 KB Output is correct
6 Correct 60 ms 46200 KB Output is correct
7 Correct 58 ms 45916 KB Output is correct
8 Correct 27 ms 45832 KB Output is correct
9 Correct 18 ms 45796 KB Output is correct
10 Correct 18 ms 45716 KB Output is correct
11 Correct 22 ms 45720 KB Output is correct
12 Correct 20 ms 45912 KB Output is correct
13 Correct 20 ms 45660 KB Output is correct
14 Correct 17 ms 45632 KB Output is correct
15 Correct 23 ms 45724 KB Output is correct
16 Correct 23 ms 45660 KB Output is correct
17 Correct 23 ms 45656 KB Output is correct
18 Correct 23 ms 45752 KB Output is correct
19 Correct 19 ms 45628 KB Output is correct
20 Correct 20 ms 45660 KB Output is correct
21 Correct 22 ms 45744 KB Output is correct
22 Correct 25 ms 45660 KB Output is correct
23 Correct 21 ms 45528 KB Output is correct
24 Correct 19 ms 45704 KB Output is correct
25 Correct 21 ms 45660 KB Output is correct
26 Correct 23 ms 45744 KB Output is correct
27 Correct 26 ms 45732 KB Output is correct
28 Correct 23 ms 45732 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 43356 KB Output is correct
2 Runtime error 1387 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 8 ms 43356 KB Output is correct
2 Runtime error 1387 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 8 ms 43356 KB Output is correct
2 Runtime error 1559 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 43352 KB Output is correct
2 Runtime error 1570 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 14 ms 43352 KB Output is correct
2 Correct 9 ms 43356 KB Output is correct
3 Correct 9 ms 43356 KB Output is correct
4 Correct 53 ms 46484 KB Output is correct
5 Correct 62 ms 46324 KB Output is correct
6 Correct 60 ms 46200 KB Output is correct
7 Correct 58 ms 45916 KB Output is correct
8 Correct 27 ms 45832 KB Output is correct
9 Correct 18 ms 45796 KB Output is correct
10 Correct 18 ms 45716 KB Output is correct
11 Correct 22 ms 45720 KB Output is correct
12 Correct 20 ms 45912 KB Output is correct
13 Correct 20 ms 45660 KB Output is correct
14 Correct 17 ms 45632 KB Output is correct
15 Correct 23 ms 45724 KB Output is correct
16 Correct 23 ms 45660 KB Output is correct
17 Correct 23 ms 45656 KB Output is correct
18 Correct 23 ms 45752 KB Output is correct
19 Correct 19 ms 45628 KB Output is correct
20 Correct 20 ms 45660 KB Output is correct
21 Correct 22 ms 45744 KB Output is correct
22 Correct 25 ms 45660 KB Output is correct
23 Correct 21 ms 45528 KB Output is correct
24 Correct 19 ms 45704 KB Output is correct
25 Correct 21 ms 45660 KB Output is correct
26 Correct 23 ms 45744 KB Output is correct
27 Correct 26 ms 45732 KB Output is correct
28 Correct 23 ms 45732 KB Output is correct
29 Correct 8 ms 43356 KB Output is correct
30 Runtime error 1387 ms 1048576 KB Execution killed with signal 9
31 Halted 0 ms 0 KB -