oj.uz

Submission #922515

# Submission time Handle Problem Language Result Execution time Memory
922515 2024-02-05T15:36:03 Z huutuan Sprinkler (JOI22_sprinkler) C++14
41 / 100
 4000 ms 805076 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][i].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][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]).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 91 ms 271444 KB Output is correct
2 Correct 60 ms 271444 KB Output is correct
3 Correct 58 ms 271392 KB Output is correct
4 Correct 62 ms 273492 KB Output is correct
5 Correct 67 ms 273956 KB Output is correct
6 Correct 72 ms 273752 KB Output is correct
7 Correct 66 ms 273748 KB Output is correct
8 Correct 73 ms 274112 KB Output is correct
9 Correct 61 ms 271500 KB Output is correct
10 Correct 57 ms 271440 KB Output is correct
11 Correct 60 ms 271504 KB Output is correct
12 Correct 57 ms 271440 KB Output is correct
13 Correct 59 ms 271440 KB Output is correct
14 Correct 60 ms 271440 KB Output is correct
15 Correct 58 ms 271448 KB Output is correct
16 Correct 59 ms 271444 KB Output is correct
17 Correct 62 ms 271480 KB Output is correct
18 Correct 59 ms 271520 KB Output is correct
19 Correct 64 ms 271476 KB Output is correct
20 Correct 59 ms 271444 KB Output is correct
21 Correct 61 ms 271444 KB Output is correct
22 Correct 62 ms 271488 KB Output is correct
23 Correct 62 ms 271932 KB Output is correct
24 Correct 62 ms 271444 KB Output is correct
25 Correct 59 ms 271440 KB Output is correct
26 Correct 59 ms 271440 KB Output is correct
27 Correct 61 ms 271272 KB Output is correct
28 Correct 61 ms 271484 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 271444 KB Output is correct
2 Correct 2097 ms 722480 KB Output is correct
3 Correct 1095 ms 722792 KB Output is correct
4 Correct 1408 ms 685280 KB Output is correct
5 Correct 1577 ms 723188 KB Output is correct
6 Correct 1050 ms 739344 KB Output is correct
7 Correct 1215 ms 752612 KB Output is correct
8 Correct 995 ms 805076 KB Output is correct
9 Correct 1764 ms 690816 KB Output is correct
10 Correct 1010 ms 689396 KB Output is correct
11 Correct 2086 ms 722552 KB Output is correct
12 Correct 1111 ms 723332 KB Output is correct
13 Correct 866 ms 792004 KB Output is correct
14 Correct 1085 ms 793240 KB Output is correct
15 Correct 1022 ms 793332 KB Output is correct
16 Correct 1020 ms 794380 KB Output is correct
17 Correct 1184 ms 793032 KB Output is correct
18 Correct 60 ms 271256 KB Output is correct
19 Correct 60 ms 271696 KB Output is correct
20 Correct 59 ms 271508 KB Output is correct
21 Correct 65 ms 271440 KB Output is correct
22 Correct 61 ms 271516 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 271444 KB Output is correct
2 Correct 2097 ms 722480 KB Output is correct
3 Correct 1095 ms 722792 KB Output is correct
4 Correct 1408 ms 685280 KB Output is correct
5 Correct 1577 ms 723188 KB Output is correct
6 Correct 1050 ms 739344 KB Output is correct
7 Correct 1215 ms 752612 KB Output is correct
8 Correct 995 ms 805076 KB Output is correct
9 Correct 1764 ms 690816 KB Output is correct
10 Correct 1010 ms 689396 KB Output is correct
11 Correct 2086 ms 722552 KB Output is correct
12 Correct 1111 ms 723332 KB Output is correct
13 Correct 866 ms 792004 KB Output is correct
14 Correct 1085 ms 793240 KB Output is correct
15 Correct 1022 ms 793332 KB Output is correct
16 Correct 1020 ms 794380 KB Output is correct
17 Correct 1184 ms 793032 KB Output is correct
18 Correct 60 ms 271256 KB Output is correct
19 Correct 60 ms 271696 KB Output is correct
20 Correct 59 ms 271508 KB Output is correct
21 Correct 65 ms 271440 KB Output is correct
22 Correct 61 ms 271516 KB Output is correct
23 Correct 60 ms 271444 KB Output is correct
24 Correct 2053 ms 722544 KB Output is correct
25 Correct 1252 ms 723264 KB Output is correct
26 Correct 1450 ms 690036 KB Output is correct
27 Correct 1602 ms 722872 KB Output is correct
28 Correct 1127 ms 739804 KB Output is correct
29 Correct 1251 ms 751936 KB Output is correct
30 Correct 1131 ms 804968 KB Output is correct
31 Correct 1775 ms 685680 KB Output is correct
32 Correct 1045 ms 689640 KB Output is correct
33 Correct 2054 ms 722508 KB Output is correct
34 Correct 1244 ms 723112 KB Output is correct
35 Correct 59 ms 271492 KB Output is correct
36 Correct 62 ms 271444 KB Output is correct
37 Correct 59 ms 271504 KB Output is correct
38 Correct 62 ms 271444 KB Output is correct
39 Correct 60 ms 271444 KB Output is correct
40 Correct 64 ms 271696 KB Output is correct
41 Correct 60 ms 271696 KB Output is correct
42 Correct 59 ms 271476 KB Output is correct
43 Correct 61 ms 271472 KB Output is correct
44 Correct 62 ms 271440 KB Output is correct
45 Correct 64 ms 271700 KB Output is correct
46 Correct 61 ms 271444 KB Output is correct
47 Correct 61 ms 271440 KB Output is correct
48 Correct 59 ms 271444 KB Output is correct
49 Correct 59 ms 271444 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 271492 KB Output is correct
2 Correct 1973 ms 687492 KB Output is correct
3 Correct 2386 ms 684320 KB Output is correct
4 Correct 1780 ms 684416 KB Output is correct
5 Correct 3848 ms 720052 KB Output is correct
6 Execution timed out 4040 ms 736972 KB Time limit exceeded
7 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 Correct 2019 ms 684928 KB Output is correct
3 Correct 2311 ms 681184 KB Output is correct
4 Correct 1829 ms 683548 KB Output is correct
5 Correct 3872 ms 721660 KB Output is correct
6 Execution timed out 4110 ms 738192 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 271444 KB Output is correct
2 Correct 60 ms 271444 KB Output is correct
3 Correct 58 ms 271392 KB Output is correct
4 Correct 62 ms 273492 KB Output is correct
5 Correct 67 ms 273956 KB Output is correct
6 Correct 72 ms 273752 KB Output is correct
7 Correct 66 ms 273748 KB Output is correct
8 Correct 73 ms 274112 KB Output is correct
9 Correct 61 ms 271500 KB Output is correct
10 Correct 57 ms 271440 KB Output is correct
11 Correct 60 ms 271504 KB Output is correct
12 Correct 57 ms 271440 KB Output is correct
13 Correct 59 ms 271440 KB Output is correct
14 Correct 60 ms 271440 KB Output is correct
15 Correct 58 ms 271448 KB Output is correct
16 Correct 59 ms 271444 KB Output is correct
17 Correct 62 ms 271480 KB Output is correct
18 Correct 59 ms 271520 KB Output is correct
19 Correct 64 ms 271476 KB Output is correct
20 Correct 59 ms 271444 KB Output is correct
21 Correct 61 ms 271444 KB Output is correct
22 Correct 62 ms 271488 KB Output is correct
23 Correct 62 ms 271932 KB Output is correct
24 Correct 62 ms 271444 KB Output is correct
25 Correct 59 ms 271440 KB Output is correct
26 Correct 59 ms 271440 KB Output is correct
27 Correct 61 ms 271272 KB Output is correct
28 Correct 61 ms 271484 KB Output is correct
29 Correct 60 ms 271444 KB Output is correct
30 Correct 2097 ms 722480 KB Output is correct
31 Correct 1095 ms 722792 KB Output is correct
32 Correct 1408 ms 685280 KB Output is correct
33 Correct 1577 ms 723188 KB Output is correct
34 Correct 1050 ms 739344 KB Output is correct
35 Correct 1215 ms 752612 KB Output is correct
36 Correct 995 ms 805076 KB Output is correct
37 Correct 1764 ms 690816 KB Output is correct
38 Correct 1010 ms 689396 KB Output is correct
39 Correct 2086 ms 722552 KB Output is correct
40 Correct 1111 ms 723332 KB Output is correct
41 Correct 866 ms 792004 KB Output is correct
42 Correct 1085 ms 793240 KB Output is correct
43 Correct 1022 ms 793332 KB Output is correct
44 Correct 1020 ms 794380 KB Output is correct
45 Correct 1184 ms 793032 KB Output is correct
46 Correct 60 ms 271256 KB Output is correct
47 Correct 60 ms 271696 KB Output is correct
48 Correct 59 ms 271508 KB Output is correct
49 Correct 65 ms 271440 KB Output is correct
50 Correct 61 ms 271516 KB Output is correct
51 Correct 60 ms 271444 KB Output is correct
52 Correct 2053 ms 722544 KB Output is correct
53 Correct 1252 ms 723264 KB Output is correct
54 Correct 1450 ms 690036 KB Output is correct
55 Correct 1602 ms 722872 KB Output is correct
56 Correct 1127 ms 739804 KB Output is correct
57 Correct 1251 ms 751936 KB Output is correct
58 Correct 1131 ms 804968 KB Output is correct
59 Correct 1775 ms 685680 KB Output is correct
60 Correct 1045 ms 689640 KB Output is correct
61 Correct 2054 ms 722508 KB Output is correct
62 Correct 1244 ms 723112 KB Output is correct
63 Correct 59 ms 271492 KB Output is correct
64 Correct 62 ms 271444 KB Output is correct
65 Correct 59 ms 271504 KB Output is correct
66 Correct 62 ms 271444 KB Output is correct
67 Correct 60 ms 271444 KB Output is correct
68 Correct 64 ms 271696 KB Output is correct
69 Correct 60 ms 271696 KB Output is correct
70 Correct 59 ms 271476 KB Output is correct
71 Correct 61 ms 271472 KB Output is correct
72 Correct 62 ms 271440 KB Output is correct
73 Correct 64 ms 271700 KB Output is correct
74 Correct 61 ms 271444 KB Output is correct
75 Correct 61 ms 271440 KB Output is correct
76 Correct 59 ms 271444 KB Output is correct
77 Correct 59 ms 271444 KB Output is correct
78 Correct 59 ms 271492 KB Output is correct
79 Correct 1973 ms 687492 KB Output is correct
80 Correct 2386 ms 684320 KB Output is correct
81 Correct 1780 ms 684416 KB Output is correct
82 Correct 3848 ms 720052 KB Output is correct
83 Execution timed out 4040 ms 736972 KB Time limit exceeded
84 Halted 0 ms 0 KB -