oj.uz

Submission #637750

# Submission time Handle Problem Language Result Execution time Memory
637750 2022-09-03T06:34:28 Z victor_gao Sprinkler (JOI22_sprinkler) C++17
12 / 100
 708 ms 117284 KB 
//#pragma GCC optimize("Ofast,unroll-loops,O3")
//#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define int long long
#define pii pair<int,int>
#define x first
#define y second
#define N 200015
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset;
//typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set;
int cnt[N][55],n,L,fa[N],h[N];
vector<int>g[N];
void dfs(int p,int lp){
    fa[p]=lp;
    for (auto i:g[p]){
        if (i!=lp){
            dfs(i,p);
        }
    }
}
signed main(){
    fast
    cin>>n>>L;
    for (int i=1;i<n;i++){
        int a,b; cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for (int i=1;i<=n;i++){
        cin>>h[i];
    }
    for (int i=0;i<=n;i++){
        for (int j=0;j<=50;j++)
            cnt[i][j]=1;
    }
    dfs(1,0);
    int q; cin>>q;
    while (q--){
        int type,x,d,w; cin>>type;
        if (type==1){
            cin>>x>>d>>w;
            for (int i=0;i<=d;i++){
                cnt[x][d-i]=cnt[x][d-i]*w%L;
                if (x==0) break;
                x=fa[x];
            }
        }
        else {
            cin>>x;
            int ans=h[x];
            for (int i=0;i<=41;i++){
                ans=(ans*cnt[x][i])%L;
                ans=(ans*cnt[x][i+1])%L;
                x=fa[x];
                if (x==0){
                    for (int j=i;j<=41;j++)
                        ans=(ans*cnt[x][j])%L;
                    break;
                }
            }
            cout<<ans<<'\n';
        }
    }
}

Subtask #1
0 / 3.0

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

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 636 ms 113420 KB Output is correct
3 Correct 406 ms 113936 KB Output is correct
4 Correct 517 ms 115696 KB Output is correct
5 Correct 508 ms 113636 KB Output is correct
6 Correct 389 ms 113228 KB Output is correct
7 Correct 363 ms 113916 KB Output is correct
8 Correct 321 ms 114124 KB Output is correct
9 Correct 708 ms 117148 KB Output is correct
10 Correct 365 ms 117284 KB Output is correct
11 Incorrect 577 ms 113248 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 636 ms 113420 KB Output is correct
3 Correct 406 ms 113936 KB Output is correct
4 Correct 517 ms 115696 KB Output is correct
5 Correct 508 ms 113636 KB Output is correct
6 Correct 389 ms 113228 KB Output is correct
7 Correct 363 ms 113916 KB Output is correct
8 Correct 321 ms 114124 KB Output is correct
9 Correct 708 ms 117148 KB Output is correct
10 Correct 365 ms 117284 KB Output is correct
11 Incorrect 577 ms 113248 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 665 ms 114308 KB Output is correct
3 Correct 695 ms 114048 KB Output is correct
4 Correct 572 ms 113612 KB Output is correct
5 Correct 563 ms 110600 KB Output is correct
6 Correct 378 ms 110804 KB Output is correct
7 Correct 351 ms 111052 KB Output is correct
8 Correct 279 ms 111252 KB Output is correct
9 Correct 658 ms 112852 KB Output is correct
10 Correct 668 ms 114384 KB Output is correct
11 Correct 602 ms 110256 KB Output is correct
12 Correct 629 ms 111264 KB Output is correct
13 Correct 397 ms 112092 KB Output is correct
14 Correct 398 ms 112844 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Incorrect 678 ms 115252 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 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Incorrect 4 ms 5460 KB Output isn't correct
5 Halted 0 ms 0 KB -