oj.uz

Submission #792118

# Submission time Handle Problem Language Result Execution time Memory
792118 2023-07-24T15:26:44 Z winter0101 Sprinkler (JOI22_sprinkler) C++14
9 / 100
 543 ms 87464 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 p[maxn];
long long h[maxn];
void dfs(int u,int par){
for (auto v:a[u]){
    if(v==par)continue;
    p[v]=u;
    //for1(j,0,40)mul[v][j]=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 dd=dis,u=x;
       if (dd==0){
        h[x]=(h[x]*w)%l;
        continue;
       }
       int diff=0;
       for1(j,0,dis){
       if (diff==dis){
        h[u]=(h[u]*w)%l;
        continue;
       }
       mul[u][dis-j]=(mul[u][dis-j]*w)%l;
       //cout<<u<<" "<<j<<'\n';
       if (p[u]!=0){
        diff++;
        if (diff==dis){
        mul[u][0]=(mul[u][0]*w)%l;
        }
        u=p[u];
       }
       }
    }
    else {
        int x;
        cin>>x;
        long long nw=h[x];
        int u=x;
        for1(j,0,40){
        nw=(nw*mul[u][j])%l;
        if (p[u]!=0)u=p[u];
        else break;
        }
        cout<<nw<<'\n';
    }
    }
    //cout<<mul[2][0];
    //for1(i,1,n)cout<<h[i]<<'\n';
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Incorrect 3 ms 5332 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 2 ms 4948 KB Output is correct
2 Correct 460 ms 83252 KB Output is correct
3 Correct 307 ms 80036 KB Output is correct
4 Correct 388 ms 84044 KB Output is correct
5 Correct 352 ms 81512 KB Output is correct
6 Correct 256 ms 81524 KB Output is correct
7 Correct 234 ms 81996 KB Output is correct
8 Correct 203 ms 82136 KB Output is correct
9 Correct 507 ms 87464 KB Output is correct
10 Correct 282 ms 83916 KB Output is correct
11 Correct 489 ms 83192 KB Output is correct
12 Correct 270 ms 80100 KB Output is correct
13 Correct 192 ms 80316 KB Output is correct
14 Correct 185 ms 80336 KB Output is correct
15 Correct 183 ms 80288 KB Output is correct
16 Correct 185 ms 80332 KB Output is correct
17 Correct 191 ms 80848 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 2 ms 4948 KB Output is correct
21 Correct 3 ms 4952 KB Output is correct
22 Correct 2 ms 4948 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 460 ms 83252 KB Output is correct
3 Correct 307 ms 80036 KB Output is correct
4 Correct 388 ms 84044 KB Output is correct
5 Correct 352 ms 81512 KB Output is correct
6 Correct 256 ms 81524 KB Output is correct
7 Correct 234 ms 81996 KB Output is correct
8 Correct 203 ms 82136 KB Output is correct
9 Correct 507 ms 87464 KB Output is correct
10 Correct 282 ms 83916 KB Output is correct
11 Correct 489 ms 83192 KB Output is correct
12 Correct 270 ms 80100 KB Output is correct
13 Correct 192 ms 80316 KB Output is correct
14 Correct 185 ms 80336 KB Output is correct
15 Correct 183 ms 80288 KB Output is correct
16 Correct 185 ms 80332 KB Output is correct
17 Correct 191 ms 80848 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 2 ms 4948 KB Output is correct
21 Correct 3 ms 4952 KB Output is correct
22 Correct 2 ms 4948 KB Output is correct
23 Correct 2 ms 4948 KB Output is correct
24 Incorrect 430 ms 83160 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 538 ms 84892 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 5040 KB Output is correct
2 Incorrect 543 ms 85700 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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