oj.uz

Submission #922531

# Submission time Handle Problem Language Result Execution time Memory
922531 2024-02-05T16:12:12 Z huutuan Sprinkler (JOI22_sprinkler) C++17
3 / 100
 4000 ms 733228 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)

int mod;

struct SegmentTree{
   int n;
   vector<pair<int, int>> t;
   void init(int _n){
      n=_n;
      t.assign(4*n+1, {1, 1});
   }
   void apply(int k, int val){
      t[k].first=1ll*t[k].first*val%mod;
      t[k].second=1ll*t[k].second*val%mod;
   }
   void push(int k){
      if (t[k].second!=1){
         apply(k<<1, t[k].second);
         apply(k<<1|1, t[k].second);
         t[k].second=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];
      t[k].first=1ll*t[k<<1].first*t[k<<1|1].first%mod;
   }
   pair<int, int> 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<=41; ++i) mult[u][i].init(g[u].size());
   tout[u]=tdfs;
}

int cnt=0;

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);
   for (int i=41-d; i<=41; i+=i&(-i)) mult[u][i].update(1, 0, isz(g[u])-1, 0, isz(g[u])-1, w), cnt+=isz(g[u]);
   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=0; i<=d; ++i){
      //    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);
      // }
      for (int i=41-d; i<=41; i+=i&(-i)){
         cnt+=isz(g[p]);
         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=1ll*val*mult[p][dist].get(1, 0, isz(g[p])-1, idx[lca]).first%mod;
      for (int i=41-dist; i; i-=i&(-i)) val=1ll*val*mult[p][i].get(1, 0, isz(g[p])-1, idx[lca]).first%mod, cnt+=isz(g[p]);
      lca=par[lca];
   }
   return val;
}

void solve(){
   #ifdef sus
   freopen("cf.inp", "r", stdin);
   freopen("cf.out", "w", stdout);
   #endif
   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';
      }
   }
   // cerr << cnt << endl;
}

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 112 ms 268100 KB Output is correct
2 Correct 115 ms 268036 KB Output is correct
3 Correct 107 ms 268084 KB Output is correct
4 Correct 118 ms 270180 KB Output is correct
5 Correct 116 ms 270412 KB Output is correct
6 Correct 127 ms 270440 KB Output is correct
7 Correct 114 ms 270512 KB Output is correct
8 Correct 111 ms 270676 KB Output is correct
9 Correct 115 ms 268204 KB Output is correct
10 Correct 110 ms 268172 KB Output is correct
11 Correct 108 ms 268116 KB Output is correct
12 Correct 109 ms 268220 KB Output is correct
13 Correct 109 ms 268112 KB Output is correct
14 Correct 109 ms 268124 KB Output is correct
15 Correct 107 ms 268108 KB Output is correct
16 Correct 110 ms 268216 KB Output is correct
17 Correct 116 ms 268064 KB Output is correct
18 Correct 108 ms 268228 KB Output is correct
19 Correct 109 ms 268148 KB Output is correct
20 Correct 116 ms 268116 KB Output is correct
21 Correct 110 ms 268108 KB Output is correct
22 Correct 109 ms 268200 KB Output is correct
23 Correct 108 ms 268112 KB Output is correct
24 Correct 112 ms 268016 KB Output is correct
25 Correct 108 ms 267980 KB Output is correct
26 Correct 108 ms 268060 KB Output is correct
27 Correct 109 ms 268112 KB Output is correct
28 Correct 108 ms 268036 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 268032 KB Output is correct
2 Execution timed out 4062 ms 733228 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 268032 KB Output is correct
2 Execution timed out 4062 ms 733228 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 268196 KB Output is correct
2 Correct 3586 ms 699652 KB Output is correct
3 Correct 2245 ms 696196 KB Output is correct
4 Correct 2803 ms 696308 KB Output is correct
5 Execution timed out 4054 ms 730832 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 268008 KB Output is correct
2 Correct 3820 ms 696548 KB Output is correct
3 Correct 2099 ms 692212 KB Output is correct
4 Correct 2839 ms 694604 KB Output is correct
5 Execution timed out 4072 ms 723792 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 268100 KB Output is correct
2 Correct 115 ms 268036 KB Output is correct
3 Correct 107 ms 268084 KB Output is correct
4 Correct 118 ms 270180 KB Output is correct
5 Correct 116 ms 270412 KB Output is correct
6 Correct 127 ms 270440 KB Output is correct
7 Correct 114 ms 270512 KB Output is correct
8 Correct 111 ms 270676 KB Output is correct
9 Correct 115 ms 268204 KB Output is correct
10 Correct 110 ms 268172 KB Output is correct
11 Correct 108 ms 268116 KB Output is correct
12 Correct 109 ms 268220 KB Output is correct
13 Correct 109 ms 268112 KB Output is correct
14 Correct 109 ms 268124 KB Output is correct
15 Correct 107 ms 268108 KB Output is correct
16 Correct 110 ms 268216 KB Output is correct
17 Correct 116 ms 268064 KB Output is correct
18 Correct 108 ms 268228 KB Output is correct
19 Correct 109 ms 268148 KB Output is correct
20 Correct 116 ms 268116 KB Output is correct
21 Correct 110 ms 268108 KB Output is correct
22 Correct 109 ms 268200 KB Output is correct
23 Correct 108 ms 268112 KB Output is correct
24 Correct 112 ms 268016 KB Output is correct
25 Correct 108 ms 267980 KB Output is correct
26 Correct 108 ms 268060 KB Output is correct
27 Correct 109 ms 268112 KB Output is correct
28 Correct 108 ms 268036 KB Output is correct
29 Correct 107 ms 268032 KB Output is correct
30 Execution timed out 4062 ms 733228 KB Time limit exceeded
31 Halted 0 ms 0 KB -