oj.uz

Submission #922586

# Submission time Handle Problem Language Result Execution time Memory
922586 2024-02-05T17:17:05 Z huutuan Sprinkler (JOI22_sprinkler) C++14
41 / 100
 4000 ms 353848 KB 
#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 44 ms 124500 KB Output is correct
2 Correct 45 ms 124500 KB Output is correct
3 Correct 46 ms 124692 KB Output is correct
4 Correct 48 ms 124756 KB Output is correct
5 Correct 47 ms 124764 KB Output is correct
6 Correct 46 ms 124628 KB Output is correct
7 Correct 46 ms 124752 KB Output is correct
8 Correct 45 ms 124752 KB Output is correct
9 Correct 47 ms 124668 KB Output is correct
10 Correct 50 ms 124724 KB Output is correct
11 Correct 45 ms 124712 KB Output is correct
12 Correct 52 ms 124496 KB Output is correct
13 Correct 45 ms 124500 KB Output is correct
14 Correct 45 ms 124496 KB Output is correct
15 Correct 45 ms 124500 KB Output is correct
16 Correct 46 ms 124500 KB Output is correct
17 Correct 45 ms 124652 KB Output is correct
18 Correct 45 ms 124500 KB Output is correct
19 Correct 45 ms 124496 KB Output is correct
20 Correct 44 ms 124508 KB Output is correct
21 Correct 44 ms 124496 KB Output is correct
22 Correct 45 ms 124500 KB Output is correct
23 Correct 44 ms 124600 KB Output is correct
24 Correct 45 ms 124496 KB Output is correct
25 Correct 44 ms 124568 KB Output is correct
26 Correct 44 ms 124500 KB Output is correct
27 Correct 44 ms 124500 KB Output is correct
28 Correct 44 ms 124500 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 124588 KB Output is correct
2 Correct 3302 ms 341928 KB Output is correct
3 Correct 907 ms 342248 KB Output is correct
4 Correct 2228 ms 350164 KB Output is correct
5 Correct 2028 ms 342280 KB Output is correct
6 Correct 882 ms 341572 KB Output is correct
7 Correct 804 ms 342220 KB Output is correct
8 Correct 445 ms 342868 KB Output is correct
9 Correct 3601 ms 353848 KB Output is correct
10 Correct 849 ms 353260 KB Output is correct
11 Correct 3149 ms 342008 KB Output is correct
12 Correct 808 ms 342384 KB Output is correct
13 Correct 363 ms 342516 KB Output is correct
14 Correct 431 ms 343004 KB Output is correct
15 Correct 435 ms 342296 KB Output is correct
16 Correct 437 ms 342868 KB Output is correct
17 Correct 466 ms 343340 KB Output is correct
18 Correct 43 ms 124500 KB Output is correct
19 Correct 42 ms 124496 KB Output is correct
20 Correct 42 ms 124584 KB Output is correct
21 Correct 42 ms 124500 KB Output is correct
22 Correct 43 ms 124624 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 124588 KB Output is correct
2 Correct 3302 ms 341928 KB Output is correct
3 Correct 907 ms 342248 KB Output is correct
4 Correct 2228 ms 350164 KB Output is correct
5 Correct 2028 ms 342280 KB Output is correct
6 Correct 882 ms 341572 KB Output is correct
7 Correct 804 ms 342220 KB Output is correct
8 Correct 445 ms 342868 KB Output is correct
9 Correct 3601 ms 353848 KB Output is correct
10 Correct 849 ms 353260 KB Output is correct
11 Correct 3149 ms 342008 KB Output is correct
12 Correct 808 ms 342384 KB Output is correct
13 Correct 363 ms 342516 KB Output is correct
14 Correct 431 ms 343004 KB Output is correct
15 Correct 435 ms 342296 KB Output is correct
16 Correct 437 ms 342868 KB Output is correct
17 Correct 466 ms 343340 KB Output is correct
18 Correct 43 ms 124500 KB Output is correct
19 Correct 42 ms 124496 KB Output is correct
20 Correct 42 ms 124584 KB Output is correct
21 Correct 42 ms 124500 KB Output is correct
22 Correct 43 ms 124624 KB Output is correct
23 Correct 44 ms 124508 KB Output is correct
24 Correct 3173 ms 341984 KB Output is correct
25 Correct 837 ms 342360 KB Output is correct
26 Correct 2175 ms 353444 KB Output is correct
27 Correct 1961 ms 342392 KB Output is correct
28 Correct 935 ms 342220 KB Output is correct
29 Correct 767 ms 342072 KB Output is correct
30 Correct 461 ms 342900 KB Output is correct
31 Correct 3641 ms 350472 KB Output is correct
32 Correct 815 ms 353228 KB Output is correct
33 Correct 3159 ms 341776 KB Output is correct
34 Correct 837 ms 342316 KB Output is correct
35 Correct 43 ms 124676 KB Output is correct
36 Correct 44 ms 124500 KB Output is correct
37 Correct 47 ms 124496 KB Output is correct
38 Correct 43 ms 124496 KB Output is correct
39 Correct 43 ms 124500 KB Output is correct
40 Correct 43 ms 124500 KB Output is correct
41 Correct 48 ms 124756 KB Output is correct
42 Correct 45 ms 124700 KB Output is correct
43 Correct 44 ms 124500 KB Output is correct
44 Correct 45 ms 124496 KB Output is correct
45 Correct 43 ms 124500 KB Output is correct
46 Correct 44 ms 124540 KB Output is correct
47 Correct 42 ms 124704 KB Output is correct
48 Correct 43 ms 124548 KB Output is correct
49 Correct 43 ms 124692 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 124500 KB Output is correct
2 Correct 3735 ms 351072 KB Output is correct
3 Correct 2274 ms 348756 KB Output is correct
4 Correct 2613 ms 348768 KB Output is correct
5 Correct 2604 ms 339136 KB Output is correct
6 Correct 1342 ms 339400 KB Output is correct
7 Correct 1149 ms 339388 KB Output is correct
8 Correct 643 ms 339868 KB Output is correct
9 Correct 3936 ms 347176 KB Output is correct
10 Correct 2273 ms 350092 KB Output is correct
11 Correct 3447 ms 338700 KB Output is correct
12 Correct 3078 ms 339976 KB Output is correct
13 Execution timed out 4033 ms 339488 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 124480 KB Output is correct
2 Correct 3869 ms 349404 KB Output is correct
3 Correct 2310 ms 346072 KB Output is correct
4 Correct 2599 ms 347856 KB Output is correct
5 Correct 2690 ms 340740 KB Output is correct
6 Correct 1266 ms 341236 KB Output is correct
7 Correct 1074 ms 340516 KB Output is correct
8 Correct 589 ms 340940 KB Output is correct
9 Correct 3701 ms 352524 KB Output is correct
10 Correct 2199 ms 351100 KB Output is correct
11 Correct 3420 ms 341444 KB Output is correct
12 Correct 3004 ms 338308 KB Output is correct
13 Execution timed out 4030 ms 337824 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 124500 KB Output is correct
2 Correct 45 ms 124500 KB Output is correct
3 Correct 46 ms 124692 KB Output is correct
4 Correct 48 ms 124756 KB Output is correct
5 Correct 47 ms 124764 KB Output is correct
6 Correct 46 ms 124628 KB Output is correct
7 Correct 46 ms 124752 KB Output is correct
8 Correct 45 ms 124752 KB Output is correct
9 Correct 47 ms 124668 KB Output is correct
10 Correct 50 ms 124724 KB Output is correct
11 Correct 45 ms 124712 KB Output is correct
12 Correct 52 ms 124496 KB Output is correct
13 Correct 45 ms 124500 KB Output is correct
14 Correct 45 ms 124496 KB Output is correct
15 Correct 45 ms 124500 KB Output is correct
16 Correct 46 ms 124500 KB Output is correct
17 Correct 45 ms 124652 KB Output is correct
18 Correct 45 ms 124500 KB Output is correct
19 Correct 45 ms 124496 KB Output is correct
20 Correct 44 ms 124508 KB Output is correct
21 Correct 44 ms 124496 KB Output is correct
22 Correct 45 ms 124500 KB Output is correct
23 Correct 44 ms 124600 KB Output is correct
24 Correct 45 ms 124496 KB Output is correct
25 Correct 44 ms 124568 KB Output is correct
26 Correct 44 ms 124500 KB Output is correct
27 Correct 44 ms 124500 KB Output is correct
28 Correct 44 ms 124500 KB Output is correct
29 Correct 47 ms 124588 KB Output is correct
30 Correct 3302 ms 341928 KB Output is correct
31 Correct 907 ms 342248 KB Output is correct
32 Correct 2228 ms 350164 KB Output is correct
33 Correct 2028 ms 342280 KB Output is correct
34 Correct 882 ms 341572 KB Output is correct
35 Correct 804 ms 342220 KB Output is correct
36 Correct 445 ms 342868 KB Output is correct
37 Correct 3601 ms 353848 KB Output is correct
38 Correct 849 ms 353260 KB Output is correct
39 Correct 3149 ms 342008 KB Output is correct
40 Correct 808 ms 342384 KB Output is correct
41 Correct 363 ms 342516 KB Output is correct
42 Correct 431 ms 343004 KB Output is correct
43 Correct 435 ms 342296 KB Output is correct
44 Correct 437 ms 342868 KB Output is correct
45 Correct 466 ms 343340 KB Output is correct
46 Correct 43 ms 124500 KB Output is correct
47 Correct 42 ms 124496 KB Output is correct
48 Correct 42 ms 124584 KB Output is correct
49 Correct 42 ms 124500 KB Output is correct
50 Correct 43 ms 124624 KB Output is correct
51 Correct 44 ms 124508 KB Output is correct
52 Correct 3173 ms 341984 KB Output is correct
53 Correct 837 ms 342360 KB Output is correct
54 Correct 2175 ms 353444 KB Output is correct
55 Correct 1961 ms 342392 KB Output is correct
56 Correct 935 ms 342220 KB Output is correct
57 Correct 767 ms 342072 KB Output is correct
58 Correct 461 ms 342900 KB Output is correct
59 Correct 3641 ms 350472 KB Output is correct
60 Correct 815 ms 353228 KB Output is correct
61 Correct 3159 ms 341776 KB Output is correct
62 Correct 837 ms 342316 KB Output is correct
63 Correct 43 ms 124676 KB Output is correct
64 Correct 44 ms 124500 KB Output is correct
65 Correct 47 ms 124496 KB Output is correct
66 Correct 43 ms 124496 KB Output is correct
67 Correct 43 ms 124500 KB Output is correct
68 Correct 43 ms 124500 KB Output is correct
69 Correct 48 ms 124756 KB Output is correct
70 Correct 45 ms 124700 KB Output is correct
71 Correct 44 ms 124500 KB Output is correct
72 Correct 45 ms 124496 KB Output is correct
73 Correct 43 ms 124500 KB Output is correct
74 Correct 44 ms 124540 KB Output is correct
75 Correct 42 ms 124704 KB Output is correct
76 Correct 43 ms 124548 KB Output is correct
77 Correct 43 ms 124692 KB Output is correct
78 Correct 43 ms 124500 KB Output is correct
79 Correct 3735 ms 351072 KB Output is correct
80 Correct 2274 ms 348756 KB Output is correct
81 Correct 2613 ms 348768 KB Output is correct
82 Correct 2604 ms 339136 KB Output is correct
83 Correct 1342 ms 339400 KB Output is correct
84 Correct 1149 ms 339388 KB Output is correct
85 Correct 643 ms 339868 KB Output is correct
86 Correct 3936 ms 347176 KB Output is correct
87 Correct 2273 ms 350092 KB Output is correct
88 Correct 3447 ms 338700 KB Output is correct
89 Correct 3078 ms 339976 KB Output is correct
90 Execution timed out 4033 ms 339488 KB Time limit exceeded
91 Halted 0 ms 0 KB -