oj.uz

Submission #922561

# Submission time Handle Problem Language Result Execution time Memory
922561 2024-02-05T16:41:37 Z huutuan Sprinkler (JOI22_sprinkler) C++14
3 / 100
 4000 ms 1029864 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 FenwickTree{
   int n;
   int mult;
   vector<int> pf, sf;
   void init(int _n){
      n=_n;
      mult=1;
      pf.assign(n+1, 1);
      sf.assign(n+1, 1);
   }
   void update(vector<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(vector<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<=41; ++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);
   for (int i=41-d; i<=41; 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=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)){
         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)<=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(idx[lca]+1)%mod;
      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';
      }
   }
}

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 222 ms 465288 KB Output is correct
2 Correct 217 ms 465324 KB Output is correct
3 Correct 242 ms 465472 KB Output is correct
4 Correct 214 ms 468160 KB Output is correct
5 Correct 208 ms 468108 KB Output is correct
6 Correct 210 ms 468012 KB Output is correct
7 Correct 205 ms 468052 KB Output is correct
8 Correct 206 ms 468504 KB Output is correct
9 Correct 202 ms 465476 KB Output is correct
10 Correct 216 ms 465540 KB Output is correct
11 Correct 202 ms 465484 KB Output is correct
12 Correct 200 ms 465496 KB Output is correct
13 Correct 203 ms 465384 KB Output is correct
14 Correct 205 ms 465384 KB Output is correct
15 Correct 202 ms 465232 KB Output is correct
16 Correct 224 ms 465604 KB Output is correct
17 Correct 200 ms 465696 KB Output is correct
18 Correct 207 ms 465508 KB Output is correct
19 Correct 204 ms 465284 KB Output is correct
20 Correct 202 ms 465472 KB Output is correct
21 Correct 204 ms 465480 KB Output is correct
22 Correct 194 ms 465688 KB Output is correct
23 Correct 192 ms 465388 KB Output is correct
24 Correct 210 ms 465472 KB Output is correct
25 Correct 200 ms 465492 KB Output is correct
26 Correct 199 ms 465288 KB Output is correct
27 Correct 202 ms 465492 KB Output is correct
28 Correct 201 ms 465496 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 465236 KB Output is correct
2 Execution timed out 4136 ms 1011256 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 465236 KB Output is correct
2 Execution timed out 4136 ms 1011256 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 465476 KB Output is correct
2 Execution timed out 4067 ms 1029864 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 465236 KB Output is correct
2 Execution timed out 4097 ms 1024192 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 465288 KB Output is correct
2 Correct 217 ms 465324 KB Output is correct
3 Correct 242 ms 465472 KB Output is correct
4 Correct 214 ms 468160 KB Output is correct
5 Correct 208 ms 468108 KB Output is correct
6 Correct 210 ms 468012 KB Output is correct
7 Correct 205 ms 468052 KB Output is correct
8 Correct 206 ms 468504 KB Output is correct
9 Correct 202 ms 465476 KB Output is correct
10 Correct 216 ms 465540 KB Output is correct
11 Correct 202 ms 465484 KB Output is correct
12 Correct 200 ms 465496 KB Output is correct
13 Correct 203 ms 465384 KB Output is correct
14 Correct 205 ms 465384 KB Output is correct
15 Correct 202 ms 465232 KB Output is correct
16 Correct 224 ms 465604 KB Output is correct
17 Correct 200 ms 465696 KB Output is correct
18 Correct 207 ms 465508 KB Output is correct
19 Correct 204 ms 465284 KB Output is correct
20 Correct 202 ms 465472 KB Output is correct
21 Correct 204 ms 465480 KB Output is correct
22 Correct 194 ms 465688 KB Output is correct
23 Correct 192 ms 465388 KB Output is correct
24 Correct 210 ms 465472 KB Output is correct
25 Correct 200 ms 465492 KB Output is correct
26 Correct 199 ms 465288 KB Output is correct
27 Correct 202 ms 465492 KB Output is correct
28 Correct 201 ms 465496 KB Output is correct
29 Correct 199 ms 465236 KB Output is correct
30 Execution timed out 4136 ms 1011256 KB Time limit exceeded
31 Halted 0 ms 0 KB -