oj.uz

Submission #792154

# Submission time Handle Problem Language Result Execution time Memory
792154 2023-07-24T16:28:45 Z winter0101 Sprinkler (JOI22_sprinkler) C++14
9 / 100
 698 ms 97032 KB 
#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define pil pair<int,long long>
#define pll pair<long long,long long>
#define eb emplace_back
#define int long long
const int maxn=2e5+9;
int n;
long long l;
vector<int>a[maxn];
long long mul[maxn][41];
int dep[maxn];
int p[maxn];
long long h[maxn];
void dfs(int u,int par){
for (auto v:a[u]){
    if(v==par)continue;
    p[v]=u;
    dep[v]=dep[u]+1;
    dfs(v,u);
}
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("temp.INP","r",stdin);
    //freopen("temp.OUT","w",stdout);
    cin>>n>>l;
    for1(i,1,n-1){
    int u,v;
    cin>>u>>v;
    a[u].pb(v);
    a[v].pb(u);
    }
    dfs(1,0);
    for1(i,1,n)cin>>h[i];
    for1(i,1,n){
    for1(j,0,40){
    mul[i][j]=1;
    }
    }
    int q;
    cin>>q;
    for1(i,1,q){
    int t;
    cin>>t;
    if (t==1){
       int x,dis;
       long long w;
       cin>>x>>dis>>w;
       int u=x;
       if (dis==0){
        h[x]=(h[x]*w)%l;
        continue;
       }
       queue<int>ver;
       int v=x;
       for1(j,0,dis){
       ver.push(v);
       if (p[v]!=0)v=p[v];
       else break;
       }
       for1(j,0,dis){
       mul[u][dis-j]=(mul[u][dis-j]*w)%l;
       int len=dis-j;
       //cout<<u<<" "<<len<<'\n';
       while (!ver.empty()){
        int t1=ver.front();
        int dd=dep[t1]-dep[u];
        //cout<<dd<<" "<<u<<'\n';
        if (dd==len){
            ver.pop();
        }
        else if (dd<len)break;
        else if (dd>len){
        h[t1]=(h[t1]*w)%l;
        //cerr<<t<<'\n';
        ver.pop();
        }
       }
       if (p[u]!=0)u=p[u];
       }
       while (!ver.empty()){
        int t1=ver.front();
        ver.pop();
        h[t1]=(h[t1]*w)%l;
        //cerr<<i<<" "<<t<<'\n';
       }
    }
    else {
        int x;
        cin>>x;
        long long nw=h[x];
        int u=x;
        for1(j,0,40){
        nw=(nw*mul[u][j])%l;
        //cout<<u<<" "<<mul[u][j]<<" "<<j<<'\n';
        if (p[u]!=0)u=p[u];
        else break;
        }
        cout<<nw<<'\n';
    }
    }
    //for1(i,1,n)cout<<h[i]<<'\n';
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 5024 KB Output is correct
4 Incorrect 3 ms 5460 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 464 ms 85164 KB Output is correct
3 Correct 301 ms 82912 KB Output is correct
4 Correct 418 ms 91376 KB Output is correct
5 Correct 406 ms 84496 KB Output is correct
6 Correct 290 ms 84520 KB Output is correct
7 Correct 262 ms 84840 KB Output is correct
8 Correct 213 ms 84864 KB Output is correct
9 Correct 522 ms 97032 KB Output is correct
10 Correct 355 ms 92980 KB Output is correct
11 Correct 444 ms 86004 KB Output is correct
12 Correct 309 ms 82912 KB Output is correct
13 Correct 236 ms 83176 KB Output is correct
14 Correct 212 ms 83332 KB Output is correct
15 Correct 216 ms 83112 KB Output is correct
16 Correct 208 ms 83048 KB Output is correct
17 Correct 217 ms 83748 KB Output is correct
18 Correct 4 ms 4948 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 3 ms 5028 KB Output is correct
21 Correct 2 ms 5076 KB Output is correct
22 Correct 3 ms 5032 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 464 ms 85164 KB Output is correct
3 Correct 301 ms 82912 KB Output is correct
4 Correct 418 ms 91376 KB Output is correct
5 Correct 406 ms 84496 KB Output is correct
6 Correct 290 ms 84520 KB Output is correct
7 Correct 262 ms 84840 KB Output is correct
8 Correct 213 ms 84864 KB Output is correct
9 Correct 522 ms 97032 KB Output is correct
10 Correct 355 ms 92980 KB Output is correct
11 Correct 444 ms 86004 KB Output is correct
12 Correct 309 ms 82912 KB Output is correct
13 Correct 236 ms 83176 KB Output is correct
14 Correct 212 ms 83332 KB Output is correct
15 Correct 216 ms 83112 KB Output is correct
16 Correct 208 ms 83048 KB Output is correct
17 Correct 217 ms 83748 KB Output is correct
18 Correct 4 ms 4948 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 3 ms 5028 KB Output is correct
21 Correct 2 ms 5076 KB Output is correct
22 Correct 3 ms 5032 KB Output is correct
23 Correct 2 ms 4948 KB Output is correct
24 Incorrect 447 ms 86100 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Incorrect 646 ms 93368 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Incorrect 698 ms 92008 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 5024 KB Output is correct
4 Incorrect 3 ms 5460 KB Output isn't correct
5 Halted 0 ms 0 KB -