oj.uz

Submission #922573

# Submission time Handle Problem Language Result Execution time Memory
922573 2024-02-05T16:58:29 Z huutuan Sprinkler (JOI22_sprinkler) C++14
38 / 100
 4000 ms 658460 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)

const int MAX_DIST=10;
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<=MAX_DIST+1; ++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=MAX_DIST+1-d; i<=MAX_DIST+1; 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=MAX_DIST+1-d; i<=MAX_DIST+1; 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)<=MAX_DIST){
      int p=par[lca];
      // val=1ll*val*mult[p][dist].get(1, 0, isz(g[p])-1, idx[lca]).first%mod;
      for (int i=MAX_DIST+1-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
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 465436 KB Output is correct
2 Correct 239 ms 465412 KB Output is correct
3 Correct 228 ms 465236 KB Output is correct
4 Execution timed out 4058 ms 466216 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 465440 KB Output is correct
2 Correct 1531 ms 637496 KB Output is correct
3 Correct 981 ms 638420 KB Output is correct
4 Correct 1322 ms 651704 KB Output is correct
5 Correct 1225 ms 638168 KB Output is correct
6 Correct 1060 ms 638828 KB Output is correct
7 Correct 967 ms 641492 KB Output is correct
8 Correct 930 ms 657604 KB Output is correct
9 Correct 1599 ms 658460 KB Output is correct
10 Correct 960 ms 657524 KB Output is correct
11 Correct 1570 ms 637028 KB Output is correct
12 Correct 1025 ms 638148 KB Output is correct
13 Correct 779 ms 655428 KB Output is correct
14 Correct 807 ms 654076 KB Output is correct
15 Correct 968 ms 655324 KB Output is correct
16 Correct 947 ms 655560 KB Output is correct
17 Correct 941 ms 656160 KB Output is correct
18 Correct 220 ms 465340 KB Output is correct
19 Correct 223 ms 465476 KB Output is correct
20 Correct 230 ms 465436 KB Output is correct
21 Correct 223 ms 465296 KB Output is correct
22 Correct 215 ms 465232 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 465440 KB Output is correct
2 Correct 1531 ms 637496 KB Output is correct
3 Correct 981 ms 638420 KB Output is correct
4 Correct 1322 ms 651704 KB Output is correct
5 Correct 1225 ms 638168 KB Output is correct
6 Correct 1060 ms 638828 KB Output is correct
7 Correct 967 ms 641492 KB Output is correct
8 Correct 930 ms 657604 KB Output is correct
9 Correct 1599 ms 658460 KB Output is correct
10 Correct 960 ms 657524 KB Output is correct
11 Correct 1570 ms 637028 KB Output is correct
12 Correct 1025 ms 638148 KB Output is correct
13 Correct 779 ms 655428 KB Output is correct
14 Correct 807 ms 654076 KB Output is correct
15 Correct 968 ms 655324 KB Output is correct
16 Correct 947 ms 655560 KB Output is correct
17 Correct 941 ms 656160 KB Output is correct
18 Correct 220 ms 465340 KB Output is correct
19 Correct 223 ms 465476 KB Output is correct
20 Correct 230 ms 465436 KB Output is correct
21 Correct 223 ms 465296 KB Output is correct
22 Correct 215 ms 465232 KB Output is correct
23 Correct 218 ms 465460 KB Output is correct
24 Correct 1679 ms 637904 KB Output is correct
25 Correct 1028 ms 638432 KB Output is correct
26 Correct 1382 ms 657644 KB Output is correct
27 Correct 1333 ms 637288 KB Output is correct
28 Correct 1137 ms 639348 KB Output is correct
29 Correct 1083 ms 641096 KB Output is correct
30 Correct 868 ms 657600 KB Output is correct
31 Correct 1661 ms 652068 KB Output is correct
32 Correct 958 ms 657700 KB Output is correct
33 Correct 1544 ms 637680 KB Output is correct
34 Correct 1079 ms 637132 KB Output is correct
35 Correct 244 ms 465396 KB Output is correct
36 Correct 227 ms 465236 KB Output is correct
37 Correct 244 ms 465348 KB Output is correct
38 Correct 222 ms 465396 KB Output is correct
39 Correct 224 ms 465296 KB Output is correct
40 Correct 228 ms 465232 KB Output is correct
41 Correct 220 ms 465252 KB Output is correct
42 Correct 221 ms 465556 KB Output is correct
43 Correct 222 ms 465468 KB Output is correct
44 Correct 219 ms 465296 KB Output is correct
45 Correct 218 ms 465536 KB Output is correct
46 Correct 237 ms 465236 KB Output is correct
47 Correct 217 ms 465492 KB Output is correct
48 Correct 220 ms 465424 KB Output is correct
49 Correct 225 ms 465268 KB Output is correct

Subtask #4
0 / 12.0

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

Subtask #5
0 / 30.0

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

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 465436 KB Output is correct
2 Correct 239 ms 465412 KB Output is correct
3 Correct 228 ms 465236 KB Output is correct
4 Execution timed out 4058 ms 466216 KB Time limit exceeded
5 Halted 0 ms 0 KB -