oj.uz

Submission #922584

# Submission time Handle Problem Language Result Execution time Memory
922584 2024-02-05T17:14:49 Z huutuan Sprinkler (JOI22_sprinkler) C++14
41 / 100
 4000 ms 356968 KB 
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2")
#include<bits/stdc++.h>

using namespace std;

// #define int long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define isz(x) ((int)x.size())
#define sumof(x) accumulate(all(x), 0ll)

const int MAX_DIST=40;
int mod;
int memory[30000000];
int sz;

struct FenwickTree{
   int n;
   int mult;
   int *pf, *sf;
   void init(int _n){
      n=_n;
      mult=1;
      pf=memory+sz;
      sz+=n;
      sf=memory+sz;
      sz+=n;
   }
   void update(int *t, int pos, int val){
      if (pos<1 || pos>n) return;
      for (int i=pos; i<=n; i+=i&(-i)) t[i]=1ll*t[i]*val%mod;
   }
   void update_all(int val){
      mult=1ll*mult*val%mod;
   }
   void update(int pos, int val){
      update(pf, n-(pos-1)+1, val);
      update(sf, pos+1, val);
   }
   int get(int *t, int pos){
      int ans=1;
      for (int i=pos; i; i-=i&(-i)) ans=1ll*ans*t[i]%mod;
      return ans;
   }
   int get(int pos){
      return 1ll*mult*get(pf, n-pos+1)%mod*get(sf, pos)%mod;
   }
};

const int N=2e5+10;
int n, q, tin[N], tout[N], tdfs, par[N], idx[N], h[N];
FenwickTree mult[N][42];
vector<int> g[N];

void dfs(int u, int p){
   par[u]=p;
   tin[u]=++tdfs;
   if (p) g[u].erase(find(all(g[u]), p));
   for (int i=0; i<isz(g[u]); ++i){
      idx[g[u][i]]=i;
      dfs(g[u][i], u);
   }
   for (int i=0; i<=MAX_DIST+1; ++i) mult[u][i].init(g[u].size());
   tout[u]=tdfs;
}

void update(int u, int d, int w){
   int lca=u;
   for (int i=MAX_DIST+1-d; i<=MAX_DIST+1; i+=i&(-i)) mult[u][i].update_all(w);
   h[u]=1ll*h[u]*w%mod;
   while (par[lca] && (--d)>=0){
      int p=par[lca];
      h[p]=1ll*h[p]*w%mod;
      int t=idx[lca];
      for (int i=MAX_DIST+1-d; i<=MAX_DIST+1; i+=i&(-i)){
         mult[p][i].update(t+1, w);
      }
      lca=par[lca];
   }
}

int query(int u){
   int val=h[u];
   int lca=u, dist=0;
   while (par[lca] && (++dist)<=MAX_DIST){
      int p=par[lca];
      for (int i=MAX_DIST+1-dist; i; i-=i&(-i)) val=1ll*val*mult[p][i].get(idx[lca]+1)%mod;
      lca=par[lca];
   }
   return val;
}

void solve(){
   fill(memory, memory+30000000, 1);
   cin >> n >> mod;
   for (int i=0; i<n-1; ++i){
      int u, v; cin >> u >> v;
      g[u].push_back(v);
      g[v].push_back(u);
   }
   dfs(1, 0);
   for (int i=1; i<=n; ++i) cin >> h[i];
   cin >> q;
   while (q--){
      int o; cin >> o;
      if (o==1){
         int u, d, w; cin >> u >> d >> w;
         update(u, d, w);
      }else{
         int u; cin >> u;
         cout << query(u) << '\n';
      }
   }
}

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   int ntests=1;
   // cin >> ntests;
   for (int i=1; i<=ntests; ++i) solve();
   return 0;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 124752 KB Output is correct
2 Correct 41 ms 124500 KB Output is correct
3 Correct 37 ms 124496 KB Output is correct
4 Correct 46 ms 124596 KB Output is correct
5 Correct 38 ms 124764 KB Output is correct
6 Correct 40 ms 124756 KB Output is correct
7 Correct 42 ms 124764 KB Output is correct
8 Correct 37 ms 124756 KB Output is correct
9 Correct 37 ms 124500 KB Output is correct
10 Correct 38 ms 124500 KB Output is correct
11 Correct 38 ms 124496 KB Output is correct
12 Correct 39 ms 124692 KB Output is correct
13 Correct 36 ms 124508 KB Output is correct
14 Correct 39 ms 124828 KB Output is correct
15 Correct 38 ms 124500 KB Output is correct
16 Correct 37 ms 124640 KB Output is correct
17 Correct 37 ms 124496 KB Output is correct
18 Correct 37 ms 124500 KB Output is correct
19 Correct 38 ms 124628 KB Output is correct
20 Correct 38 ms 124500 KB Output is correct
21 Correct 36 ms 124504 KB Output is correct
22 Correct 36 ms 124508 KB Output is correct
23 Correct 38 ms 124520 KB Output is correct
24 Correct 37 ms 124496 KB Output is correct
25 Correct 36 ms 124600 KB Output is correct
26 Correct 37 ms 124508 KB Output is correct
27 Correct 36 ms 124500 KB Output is correct
28 Correct 40 ms 124500 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 124508 KB Output is correct
2 Correct 3149 ms 341844 KB Output is correct
3 Correct 761 ms 342688 KB Output is correct
4 Correct 2233 ms 352076 KB Output is correct
5 Correct 1980 ms 342328 KB Output is correct
6 Correct 857 ms 341692 KB Output is correct
7 Correct 789 ms 342312 KB Output is correct
8 Correct 454 ms 342808 KB Output is correct
9 Correct 3577 ms 356968 KB Output is correct
10 Correct 783 ms 355928 KB Output is correct
11 Correct 3043 ms 341984 KB Output is correct
12 Correct 786 ms 342420 KB Output is correct
13 Correct 348 ms 342464 KB Output is correct
14 Correct 427 ms 342936 KB Output is correct
15 Correct 426 ms 342300 KB Output is correct
16 Correct 461 ms 342848 KB Output is correct
17 Correct 452 ms 343280 KB Output is correct
18 Correct 36 ms 124496 KB Output is correct
19 Correct 37 ms 124508 KB Output is correct
20 Correct 38 ms 124644 KB Output is correct
21 Correct 36 ms 124764 KB Output is correct
22 Correct 36 ms 124548 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 124508 KB Output is correct
2 Correct 3149 ms 341844 KB Output is correct
3 Correct 761 ms 342688 KB Output is correct
4 Correct 2233 ms 352076 KB Output is correct
5 Correct 1980 ms 342328 KB Output is correct
6 Correct 857 ms 341692 KB Output is correct
7 Correct 789 ms 342312 KB Output is correct
8 Correct 454 ms 342808 KB Output is correct
9 Correct 3577 ms 356968 KB Output is correct
10 Correct 783 ms 355928 KB Output is correct
11 Correct 3043 ms 341984 KB Output is correct
12 Correct 786 ms 342420 KB Output is correct
13 Correct 348 ms 342464 KB Output is correct
14 Correct 427 ms 342936 KB Output is correct
15 Correct 426 ms 342300 KB Output is correct
16 Correct 461 ms 342848 KB Output is correct
17 Correct 452 ms 343280 KB Output is correct
18 Correct 36 ms 124496 KB Output is correct
19 Correct 37 ms 124508 KB Output is correct
20 Correct 38 ms 124644 KB Output is correct
21 Correct 36 ms 124764 KB Output is correct
22 Correct 36 ms 124548 KB Output is correct
23 Correct 35 ms 124500 KB Output is correct
24 Correct 3259 ms 341912 KB Output is correct
25 Correct 880 ms 342244 KB Output is correct
26 Correct 2202 ms 356752 KB Output is correct
27 Correct 1946 ms 342068 KB Output is correct
28 Correct 946 ms 342152 KB Output is correct
29 Correct 774 ms 342028 KB Output is correct
30 Correct 511 ms 342800 KB Output is correct
31 Correct 3657 ms 352152 KB Output is correct
32 Correct 811 ms 356036 KB Output is correct
33 Correct 3177 ms 341684 KB Output is correct
34 Correct 851 ms 342608 KB Output is correct
35 Correct 39 ms 124500 KB Output is correct
36 Correct 37 ms 124504 KB Output is correct
37 Correct 36 ms 124500 KB Output is correct
38 Correct 37 ms 124500 KB Output is correct
39 Correct 36 ms 124508 KB Output is correct
40 Correct 37 ms 124496 KB Output is correct
41 Correct 38 ms 124692 KB Output is correct
42 Correct 36 ms 124760 KB Output is correct
43 Correct 37 ms 124760 KB Output is correct
44 Correct 37 ms 124500 KB Output is correct
45 Correct 36 ms 124500 KB Output is correct
46 Correct 38 ms 124724 KB Output is correct
47 Correct 37 ms 124508 KB Output is correct
48 Correct 37 ms 124608 KB Output is correct
49 Correct 39 ms 124500 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 124656 KB Output is correct
2 Correct 3797 ms 353760 KB Output is correct
3 Correct 2179 ms 350836 KB Output is correct
4 Correct 2594 ms 351072 KB Output is correct
5 Correct 2754 ms 339156 KB Output is correct
6 Correct 1282 ms 339236 KB Output is correct
7 Correct 1010 ms 339796 KB Output is correct
8 Correct 623 ms 339740 KB Output is correct
9 Correct 3686 ms 349476 KB Output is correct
10 Correct 2158 ms 353264 KB Output is correct
11 Correct 3630 ms 338968 KB Output is correct
12 Correct 3103 ms 339816 KB Output is correct
13 Execution timed out 4051 ms 338988 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 124500 KB Output is correct
2 Correct 3779 ms 351896 KB Output is correct
3 Correct 2174 ms 347804 KB Output is correct
4 Correct 2570 ms 349888 KB Output is correct
5 Correct 2767 ms 340724 KB Output is correct
6 Correct 1283 ms 340768 KB Output is correct
7 Correct 1140 ms 340580 KB Output is correct
8 Correct 675 ms 340756 KB Output is correct
9 Correct 3826 ms 355824 KB Output is correct
10 Correct 2163 ms 354148 KB Output is correct
11 Correct 3549 ms 341636 KB Output is correct
12 Correct 3102 ms 339904 KB Output is correct
13 Execution timed out 4026 ms 339204 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 124752 KB Output is correct
2 Correct 41 ms 124500 KB Output is correct
3 Correct 37 ms 124496 KB Output is correct
4 Correct 46 ms 124596 KB Output is correct
5 Correct 38 ms 124764 KB Output is correct
6 Correct 40 ms 124756 KB Output is correct
7 Correct 42 ms 124764 KB Output is correct
8 Correct 37 ms 124756 KB Output is correct
9 Correct 37 ms 124500 KB Output is correct
10 Correct 38 ms 124500 KB Output is correct
11 Correct 38 ms 124496 KB Output is correct
12 Correct 39 ms 124692 KB Output is correct
13 Correct 36 ms 124508 KB Output is correct
14 Correct 39 ms 124828 KB Output is correct
15 Correct 38 ms 124500 KB Output is correct
16 Correct 37 ms 124640 KB Output is correct
17 Correct 37 ms 124496 KB Output is correct
18 Correct 37 ms 124500 KB Output is correct
19 Correct 38 ms 124628 KB Output is correct
20 Correct 38 ms 124500 KB Output is correct
21 Correct 36 ms 124504 KB Output is correct
22 Correct 36 ms 124508 KB Output is correct
23 Correct 38 ms 124520 KB Output is correct
24 Correct 37 ms 124496 KB Output is correct
25 Correct 36 ms 124600 KB Output is correct
26 Correct 37 ms 124508 KB Output is correct
27 Correct 36 ms 124500 KB Output is correct
28 Correct 40 ms 124500 KB Output is correct
29 Correct 37 ms 124508 KB Output is correct
30 Correct 3149 ms 341844 KB Output is correct
31 Correct 761 ms 342688 KB Output is correct
32 Correct 2233 ms 352076 KB Output is correct
33 Correct 1980 ms 342328 KB Output is correct
34 Correct 857 ms 341692 KB Output is correct
35 Correct 789 ms 342312 KB Output is correct
36 Correct 454 ms 342808 KB Output is correct
37 Correct 3577 ms 356968 KB Output is correct
38 Correct 783 ms 355928 KB Output is correct
39 Correct 3043 ms 341984 KB Output is correct
40 Correct 786 ms 342420 KB Output is correct
41 Correct 348 ms 342464 KB Output is correct
42 Correct 427 ms 342936 KB Output is correct
43 Correct 426 ms 342300 KB Output is correct
44 Correct 461 ms 342848 KB Output is correct
45 Correct 452 ms 343280 KB Output is correct
46 Correct 36 ms 124496 KB Output is correct
47 Correct 37 ms 124508 KB Output is correct
48 Correct 38 ms 124644 KB Output is correct
49 Correct 36 ms 124764 KB Output is correct
50 Correct 36 ms 124548 KB Output is correct
51 Correct 35 ms 124500 KB Output is correct
52 Correct 3259 ms 341912 KB Output is correct
53 Correct 880 ms 342244 KB Output is correct
54 Correct 2202 ms 356752 KB Output is correct
55 Correct 1946 ms 342068 KB Output is correct
56 Correct 946 ms 342152 KB Output is correct
57 Correct 774 ms 342028 KB Output is correct
58 Correct 511 ms 342800 KB Output is correct
59 Correct 3657 ms 352152 KB Output is correct
60 Correct 811 ms 356036 KB Output is correct
61 Correct 3177 ms 341684 KB Output is correct
62 Correct 851 ms 342608 KB Output is correct
63 Correct 39 ms 124500 KB Output is correct
64 Correct 37 ms 124504 KB Output is correct
65 Correct 36 ms 124500 KB Output is correct
66 Correct 37 ms 124500 KB Output is correct
67 Correct 36 ms 124508 KB Output is correct
68 Correct 37 ms 124496 KB Output is correct
69 Correct 38 ms 124692 KB Output is correct
70 Correct 36 ms 124760 KB Output is correct
71 Correct 37 ms 124760 KB Output is correct
72 Correct 37 ms 124500 KB Output is correct
73 Correct 36 ms 124500 KB Output is correct
74 Correct 38 ms 124724 KB Output is correct
75 Correct 37 ms 124508 KB Output is correct
76 Correct 37 ms 124608 KB Output is correct
77 Correct 39 ms 124500 KB Output is correct
78 Correct 36 ms 124656 KB Output is correct
79 Correct 3797 ms 353760 KB Output is correct
80 Correct 2179 ms 350836 KB Output is correct
81 Correct 2594 ms 351072 KB Output is correct
82 Correct 2754 ms 339156 KB Output is correct
83 Correct 1282 ms 339236 KB Output is correct
84 Correct 1010 ms 339796 KB Output is correct
85 Correct 623 ms 339740 KB Output is correct
86 Correct 3686 ms 349476 KB Output is correct
87 Correct 2158 ms 353264 KB Output is correct
88 Correct 3630 ms 338968 KB Output is correct
89 Correct 3103 ms 339816 KB Output is correct
90 Execution timed out 4051 ms 338988 KB Time limit exceeded
91 Halted 0 ms 0 KB -