oj.uz

Submission #922529

# Submission time Handle Problem Language Result Execution time Memory
922529 2024-02-05T16:11:16 Z huutuan Sprinkler (JOI22_sprinkler) C++14
3 / 100
 4000 ms 732976 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 121 ms 268152 KB Output is correct
2 Correct 122 ms 268116 KB Output is correct
3 Correct 126 ms 267968 KB Output is correct
4 Correct 134 ms 270228 KB Output is correct
5 Correct 118 ms 270488 KB Output is correct
6 Correct 119 ms 270440 KB Output is correct
7 Correct 120 ms 270616 KB Output is correct
8 Correct 118 ms 270672 KB Output is correct
9 Correct 121 ms 268060 KB Output is correct
10 Correct 114 ms 268208 KB Output is correct
11 Correct 113 ms 268216 KB Output is correct
12 Correct 115 ms 268160 KB Output is correct
13 Correct 115 ms 268084 KB Output is correct
14 Correct 114 ms 268152 KB Output is correct
15 Correct 118 ms 268112 KB Output is correct
16 Correct 118 ms 268216 KB Output is correct
17 Correct 115 ms 268080 KB Output is correct
18 Correct 116 ms 268112 KB Output is correct
19 Correct 116 ms 268112 KB Output is correct
20 Correct 113 ms 268112 KB Output is correct
21 Correct 114 ms 268084 KB Output is correct
22 Correct 115 ms 267968 KB Output is correct
23 Correct 115 ms 268116 KB Output is correct
24 Correct 120 ms 268048 KB Output is correct
25 Correct 130 ms 268024 KB Output is correct
26 Correct 115 ms 268116 KB Output is correct
27 Correct 112 ms 268148 KB Output is correct
28 Correct 114 ms 268116 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 268108 KB Output is correct
2 Execution timed out 4030 ms 732976 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 268108 KB Output is correct
2 Execution timed out 4030 ms 732976 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 268196 KB Output is correct
2 Correct 3877 ms 699628 KB Output is correct
3 Correct 2157 ms 695984 KB Output is correct
4 Correct 2826 ms 696684 KB Output is correct
5 Execution timed out 4043 ms 730172 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 268108 KB Output is correct
2 Correct 3742 ms 696160 KB Output is correct
3 Correct 2124 ms 691924 KB Output is correct
4 Correct 2851 ms 694420 KB Output is correct
5 Execution timed out 4120 ms 731460 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 268152 KB Output is correct
2 Correct 122 ms 268116 KB Output is correct
3 Correct 126 ms 267968 KB Output is correct
4 Correct 134 ms 270228 KB Output is correct
5 Correct 118 ms 270488 KB Output is correct
6 Correct 119 ms 270440 KB Output is correct
7 Correct 120 ms 270616 KB Output is correct
8 Correct 118 ms 270672 KB Output is correct
9 Correct 121 ms 268060 KB Output is correct
10 Correct 114 ms 268208 KB Output is correct
11 Correct 113 ms 268216 KB Output is correct
12 Correct 115 ms 268160 KB Output is correct
13 Correct 115 ms 268084 KB Output is correct
14 Correct 114 ms 268152 KB Output is correct
15 Correct 118 ms 268112 KB Output is correct
16 Correct 118 ms 268216 KB Output is correct
17 Correct 115 ms 268080 KB Output is correct
18 Correct 116 ms 268112 KB Output is correct
19 Correct 116 ms 268112 KB Output is correct
20 Correct 113 ms 268112 KB Output is correct
21 Correct 114 ms 268084 KB Output is correct
22 Correct 115 ms 267968 KB Output is correct
23 Correct 115 ms 268116 KB Output is correct
24 Correct 120 ms 268048 KB Output is correct
25 Correct 130 ms 268024 KB Output is correct
26 Correct 115 ms 268116 KB Output is correct
27 Correct 112 ms 268148 KB Output is correct
28 Correct 114 ms 268116 KB Output is correct
29 Correct 113 ms 268108 KB Output is correct
30 Execution timed out 4030 ms 732976 KB Time limit exceeded
31 Halted 0 ms 0 KB -