oj.uz

Submission #922513

# Submission time Handle Problem Language Result Execution time Memory
922513 2024-02-05T15:28:49 Z huutuan Sprinkler (JOI22_sprinkler) C++14
3 / 100
 693 ms 1048576 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)

int mod;

struct Node{
   int val, lazy;
   Node (int t=1){
      val=t;
      lazy=1;
   }
   Node operator+(Node b){
      return Node(val*b.val%mod);
   }
};

struct SegmentTree{
   int n;
   vector<Node> t;
   void init(int _n){
      n=_n;
      t.assign(4*n+1, Node());
   }
   void apply(int k, int val){
      t[k].val=t[k].val*val%mod;
      t[k].lazy=t[k].lazy*val%mod;
   }
   void push(int k){
      if (t[k].lazy!=1){
         apply(k<<1, t[k].lazy);
         apply(k<<1|1, t[k].lazy);
         t[k].lazy=1;
      }
   }
   void update(int k, int l, int r, int L, int R, int val){
      if (r<L || R<l) return;
      if (L<=l && r<=R){
         apply(k, val);
         return;
      }
      push(k);
      int mid=(l+r)>>1;
      update(k<<1, l, mid, L, R, val);
      update(k<<1|1, mid+1, r, L, R, val);
      t[k]=t[k<<1]+t[k<<1|1];
   }
   Node get(int k, int l, int r, int pos){
      if (l==r) return t[k];
      push(k);
      int mid=(l+r)>>1;
      if (pos<=mid) return get(k<<1, l, mid, pos);
      return get(k<<1|1, mid+1, r, pos);
   }
};

const int N=2e5+10;
int n, q, tin[N], tout[N], tdfs, par[N], idx[N], h[N];
SegmentTree 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<=40; ++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=0; i<=d; ++i) mult[u][i].update(1, 0, isz(g[u])-1, 0, isz(g[u])-1, w);
   h[u]=h[u]*w%mod;
   while (par[lca] && (--d)>=0){
      int p=par[lca];
      h[p]=h[p]*w%mod;
      for (int i=0; i<=d; ++i){
         int t=idx[lca];
         mult[p][i].update(1, 0, isz(g[p])-1, 0, t-1, w);
         mult[p][i].update(1, 0, isz(g[p])-1, t+1, isz(g[p])-1, w);
      }
      lca=par[lca];
   }
}

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

void solve(){
   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 88 ms 273468 KB Output is correct
2 Correct 59 ms 273556 KB Output is correct
3 Correct 58 ms 273492 KB Output is correct
4 Correct 64 ms 277328 KB Output is correct
5 Correct 66 ms 277348 KB Output is correct
6 Correct 70 ms 277324 KB Output is correct
7 Correct 69 ms 277328 KB Output is correct
8 Correct 68 ms 277332 KB Output is correct
9 Correct 61 ms 273392 KB Output is correct
10 Correct 62 ms 273492 KB Output is correct
11 Correct 59 ms 273524 KB Output is correct
12 Correct 58 ms 273596 KB Output is correct
13 Correct 61 ms 273440 KB Output is correct
14 Correct 59 ms 273492 KB Output is correct
15 Correct 64 ms 273568 KB Output is correct
16 Correct 58 ms 273532 KB Output is correct
17 Correct 59 ms 273488 KB Output is correct
18 Correct 67 ms 273488 KB Output is correct
19 Correct 70 ms 273504 KB Output is correct
20 Correct 58 ms 273492 KB Output is correct
21 Correct 59 ms 273572 KB Output is correct
22 Correct 60 ms 273492 KB Output is correct
23 Correct 61 ms 273600 KB Output is correct
24 Correct 78 ms 273488 KB Output is correct
25 Correct 60 ms 273492 KB Output is correct
26 Correct 59 ms 273488 KB Output is correct
27 Correct 59 ms 273496 KB Output is correct
28 Correct 71 ms 273580 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 273748 KB Output is correct
2 Runtime error 693 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 273748 KB Output is correct
2 Runtime error 693 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 273332 KB Output is correct
2 Runtime error 691 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 273540 KB Output is correct
2 Runtime error 652 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 273468 KB Output is correct
2 Correct 59 ms 273556 KB Output is correct
3 Correct 58 ms 273492 KB Output is correct
4 Correct 64 ms 277328 KB Output is correct
5 Correct 66 ms 277348 KB Output is correct
6 Correct 70 ms 277324 KB Output is correct
7 Correct 69 ms 277328 KB Output is correct
8 Correct 68 ms 277332 KB Output is correct
9 Correct 61 ms 273392 KB Output is correct
10 Correct 62 ms 273492 KB Output is correct
11 Correct 59 ms 273524 KB Output is correct
12 Correct 58 ms 273596 KB Output is correct
13 Correct 61 ms 273440 KB Output is correct
14 Correct 59 ms 273492 KB Output is correct
15 Correct 64 ms 273568 KB Output is correct
16 Correct 58 ms 273532 KB Output is correct
17 Correct 59 ms 273488 KB Output is correct
18 Correct 67 ms 273488 KB Output is correct
19 Correct 70 ms 273504 KB Output is correct
20 Correct 58 ms 273492 KB Output is correct
21 Correct 59 ms 273572 KB Output is correct
22 Correct 60 ms 273492 KB Output is correct
23 Correct 61 ms 273600 KB Output is correct
24 Correct 78 ms 273488 KB Output is correct
25 Correct 60 ms 273492 KB Output is correct
26 Correct 59 ms 273488 KB Output is correct
27 Correct 59 ms 273496 KB Output is correct
28 Correct 71 ms 273580 KB Output is correct
29 Correct 59 ms 273748 KB Output is correct
30 Runtime error 693 ms 1048576 KB Execution killed with signal 9
31 Halted 0 ms 0 KB -