oj.uz

Submission #648621

# Submission time Handle Problem Language Result Execution time Memory
648621 2022-10-07T07:49:44 Z PoonYaPat Sprinkler (JOI22_sprinkler) C++14
12 / 100
 720 ms 93768 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n,q,p[200001];
ll h[200001],mul[200001][42],mod;
vector<int> adj[200001];

void dfs(int x, int par) {
    p[x]=par;
    for (auto s : adj[x]) if (s!=par) dfs(s,x);
}

void add(int node, int dis, ll val) {
    while (node!=0 && dis!=-1) {
        mul[node][dis]=(mul[node][dis]*val)%mod;
        node=p[node];
        --dis;
    }
}

void find(int node) {
    int dis=0,pre;
    ll ans=h[node];
    while (dis<=40 && node!=0) {
        ans=(ans*mul[node][dis])%mod;
        ans=(ans*mul[node][dis+1])%mod;
        pre=node;
        ++dis; node=p[node];
    }
    for (int i=dis; i<=40; ++i) { //distance can higher than root
        ans=(ans*mul[pre][i])%mod;
    }
    cout<<ans<<"\n";
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>mod;
    for (int i=1; i<=n; ++i) {
        for (int j=0; j<=41; ++j) mul[i][j]=1;
    }
    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];
    dfs(1,0);
    cin>>q;
    while (q--) {
        int mode; cin>>mode;
        if (mode==1) {
            int node,dis;
            ll w;
            cin>>node>>dis>>w;
            add(node,dis,w);
        } else {
            int node; cin>>node;
            find(node);
        }
    }
}

Compilation message

sprinkler.cpp: In function 'void find(int)':
sprinkler.cpp:32:28: warning: 'pre' may be used uninitialized in this function [-Wmaybe-uninitialized]
   32 |         ans=(ans*mul[pre][i])%mod;
      |                  ~~~~~~~~~~^

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 4 ms 5032 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 624 ms 82936 KB Output is correct
3 Correct 356 ms 79992 KB Output is correct
4 Correct 550 ms 84200 KB Output is correct
5 Correct 528 ms 81344 KB Output is correct
6 Correct 367 ms 81272 KB Output is correct
7 Correct 401 ms 81740 KB Output is correct
8 Correct 305 ms 82112 KB Output is correct
9 Correct 640 ms 87172 KB Output is correct
10 Correct 470 ms 83800 KB Output is correct
11 Incorrect 612 ms 82968 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 624 ms 82936 KB Output is correct
3 Correct 356 ms 79992 KB Output is correct
4 Correct 550 ms 84200 KB Output is correct
5 Correct 528 ms 81344 KB Output is correct
6 Correct 367 ms 81272 KB Output is correct
7 Correct 401 ms 81740 KB Output is correct
8 Correct 305 ms 82112 KB Output is correct
9 Correct 640 ms 87172 KB Output is correct
10 Correct 470 ms 83800 KB Output is correct
11 Incorrect 612 ms 82968 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 659 ms 84560 KB Output is correct
3 Correct 631 ms 92212 KB Output is correct
4 Correct 615 ms 91796 KB Output is correct
5 Correct 560 ms 88524 KB Output is correct
6 Correct 377 ms 88548 KB Output is correct
7 Correct 386 ms 88788 KB Output is correct
8 Correct 297 ms 89280 KB Output is correct
9 Correct 640 ms 91344 KB Output is correct
10 Correct 671 ms 92616 KB Output is correct
11 Correct 622 ms 88064 KB Output is correct
12 Correct 551 ms 88992 KB Output is correct
13 Correct 387 ms 90060 KB Output is correct
14 Correct 399 ms 90436 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 5 ms 4948 KB Output is correct
17 Correct 4 ms 4948 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 5 ms 5032 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 720 ms 93768 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 4 ms 4948 KB Output is correct
3 Correct 4 ms 5032 KB Output is correct
4 Incorrect 4 ms 5460 KB Output isn't correct
5 Halted 0 ms 0 KB -