oj.uz

Submission #922516

# Submission time Handle Problem Language Result Execution time Memory
922516 2024-02-05T15:40:09 Z huutuan Sprinkler (JOI22_sprinkler) C++14
3 / 100
 4000 ms 712676 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(1ll*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=1ll*t[k].val*val%mod;
      t[k].lazy=1ll*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][d].update(1, 0, isz(g[u])-1, 0, isz(g[u])-1, w);
   h[u]=1ll*h[u]*w%mod;
   while (par[lca] && (--d)>=0){
      int p=par[lca];
      h[p]=1ll*h[p]*w%mod;
      // for (int i=0; i<=d; ++i){
         int t=idx[lca];
         mult[p][d].update(1, 0, isz(g[p])-1, 0, t-1, w);
         mult[p][d].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];
      for (int i=dist; i<=40; ++i) val=1ll*val*mult[p][i].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 61 ms 271440 KB Output is correct
2 Correct 59 ms 271256 KB Output is correct
3 Correct 61 ms 271444 KB Output is correct
4 Correct 65 ms 273236 KB Output is correct
5 Correct 66 ms 273680 KB Output is correct
6 Correct 66 ms 273756 KB Output is correct
7 Correct 64 ms 273748 KB Output is correct
8 Correct 65 ms 274000 KB Output is correct
9 Correct 59 ms 271448 KB Output is correct
10 Correct 59 ms 271444 KB Output is correct
11 Correct 59 ms 271444 KB Output is correct
12 Correct 60 ms 271440 KB Output is correct
13 Correct 62 ms 271448 KB Output is correct
14 Correct 59 ms 271288 KB Output is correct
15 Correct 59 ms 271440 KB Output is correct
16 Correct 59 ms 271500 KB Output is correct
17 Correct 60 ms 271504 KB Output is correct
18 Correct 61 ms 271440 KB Output is correct
19 Correct 60 ms 271444 KB Output is correct
20 Correct 58 ms 271488 KB Output is correct
21 Correct 61 ms 271440 KB Output is correct
22 Correct 63 ms 271484 KB Output is correct
23 Correct 61 ms 271440 KB Output is correct
24 Correct 59 ms 271444 KB Output is correct
25 Correct 64 ms 271440 KB Output is correct
26 Correct 62 ms 271444 KB Output is correct
27 Correct 59 ms 271452 KB Output is correct
28 Correct 64 ms 271512 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 271492 KB Output is correct
2 Execution timed out 4054 ms 712676 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 271492 KB Output is correct
2 Execution timed out 4054 ms 712676 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 271452 KB Output is correct
2 Execution timed out 4042 ms 685356 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 271444 KB Output is correct
2 Execution timed out 4042 ms 682064 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 271440 KB Output is correct
2 Correct 59 ms 271256 KB Output is correct
3 Correct 61 ms 271444 KB Output is correct
4 Correct 65 ms 273236 KB Output is correct
5 Correct 66 ms 273680 KB Output is correct
6 Correct 66 ms 273756 KB Output is correct
7 Correct 64 ms 273748 KB Output is correct
8 Correct 65 ms 274000 KB Output is correct
9 Correct 59 ms 271448 KB Output is correct
10 Correct 59 ms 271444 KB Output is correct
11 Correct 59 ms 271444 KB Output is correct
12 Correct 60 ms 271440 KB Output is correct
13 Correct 62 ms 271448 KB Output is correct
14 Correct 59 ms 271288 KB Output is correct
15 Correct 59 ms 271440 KB Output is correct
16 Correct 59 ms 271500 KB Output is correct
17 Correct 60 ms 271504 KB Output is correct
18 Correct 61 ms 271440 KB Output is correct
19 Correct 60 ms 271444 KB Output is correct
20 Correct 58 ms 271488 KB Output is correct
21 Correct 61 ms 271440 KB Output is correct
22 Correct 63 ms 271484 KB Output is correct
23 Correct 61 ms 271440 KB Output is correct
24 Correct 59 ms 271444 KB Output is correct
25 Correct 64 ms 271440 KB Output is correct
26 Correct 62 ms 271444 KB Output is correct
27 Correct 59 ms 271452 KB Output is correct
28 Correct 64 ms 271512 KB Output is correct
29 Correct 60 ms 271492 KB Output is correct
30 Execution timed out 4054 ms 712676 KB Time limit exceeded
31 Halted 0 ms 0 KB -