oj.uz

Submission #588779

# Submission time Handle Problem Language Result Execution time Memory
588779 2022-07-04T04:38:47 Z balbit Sprinkler (JOI22_sprinkler) C++14
100 / 100
 1601 ms 270348 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define int ll
#define pii pair<ll, ll>
#define f first
#define s second

#define FOR(i,a,b) for (int i = a; i<b; ++i)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) FOR(i,1,n+1)

#define MX(a,b) a = max(a,b)
#define MN(a,b) a = min(a,b)
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
#define pb push_back

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<"- "<<#__VA_ARGS__<<": ", _do(__VA_ARGS__)
template<typename T> void _do( T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do( T && x, S && ...y) {cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
#define endl '\n'
#endif // BALBIT

const int maxn = 2e5+5;
signed L;
vector<int> rawt[maxn], g[maxn];
int par[maxn];
ll H[maxn];
int ordpos[maxn], dep[maxn];
vector<int> depv[maxn];

ll seg[maxn*4], tg[maxn*4];

inline void push(int o, int l, int r) {
    if (tg[o] != 1) {
        seg[o] *= tg[o]; seg[o] %= L;
        if (l!=r) {
            tg[o*2] = tg[o*2] * tg[o] % L;
            tg[o*2+1] = tg[o*2+1] * tg[o] % L;
        }
        tg[o] = 1;
    }
}

void MO(int L, int R, int v, int o=1, int l=0, int r=maxn-1) {
    push(o,l,r);
    if (l > R || r < L) return;
    if (l >= L && r <= R) {
        tg[o] = tg[o] * v % ::L;
        push(o,l,r); return;
    }
    int mid = (l+r)/2;
    MO(L,R,v,o*2,l,mid); MO(L,R,v,o*2+1,mid+1,r);
    seg[o] = seg[o*2] * seg[o*2+1] % ::L;
}

ll get(int p, int o=1, int l=0, int r=maxn-1) {
    if (l > p || r < p) assert(0);
    push(o,l,r);
    if (l == r) return seg[o];
    int mid = (l+r)/2;
    if (p <= mid) return get(p,o*2,l,mid);
    else return get(p,o*2+1,mid+1,r);
}

ll tomul[maxn][41];

void build(){
    fill(seg, seg+maxn*4, 1);
    fill(tg, tg+maxn*4, 1);
}

void dfs1(int v, int p) {
    par[v] = p;
    depv[dep[v]].pb(v);
    for (int u : rawt[v]) {
        if (u == p) continue;
        g[v].pb(u);
        dep[u] = dep[v] + 1;
        dfs1(u,v);
    }
}

pii rnghere[maxn][41];

void dfs2(int v) {
    fill(rnghere[v], rnghere[v]+41, pii{10000000,-1});
    rnghere[v][0] = {ordpos[v],ordpos[v]};
    for (int u : g[v]) {
        dfs2(u);
        REP(d, 40) {
            if (rnghere[u][d].s != -1) {
                MN(rnghere[v][d+1].f, rnghere[u][d].f);
                MX(rnghere[v][d+1].s, rnghere[u][d].s);
            }
        }
    }
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0);
    bug(1,2);

    int n; cin>>n>>L;
    REP(i,n-1) {
        int a,b; cin>>a>>b; --a; --b;
        rawt[a].pb(b);
        rawt[b].pb(a);
    }

    dfs1(0,-1);
    int IT = 0;
    REP(i, maxn) {
        for (int e : depv[i]) {
            bug(e, IT);
            ordpos[e] = IT++;
        }
    }
    build();

    dfs2(0);

    REP(i,n) REP(j,41) tomul[i][j] = 1;

    REP(i,n) {
        cin>>H[i];
//        , MO(ordpos[i],ordpos[i],H[i]);
        tomul[i][0] = H[i];
    }
    int q; cin>>q;
    while (q--) {
        int tp; cin>>tp;
        if (tp == 1) {
            int v, d, w; cin>>v>>d>>w; --v;
            int at = v;
            for (int dp = dep[v] + d; dp >= dep[v] - d; dp--) {
                if (dp < 0 || dp >= maxn || SZ(depv[dp]) == 0) continue;
                while (at != 0 && dep[v] - dep[par[at]] + dp - dep[par[at]] <= d) {
                    at = par[at];
                }
//                pii ha = rnghere[at][dp-dep[at]];
//                if (ha.f == -1) continue;
//                bug(ha.f, ha.s, w);
//                MO(ha.f, ha.s, w);
                (tomul[at][dp-dep[at]] *= w) %= L;
            }
        }else{
            int v; cin>>v; --v;
//            bug(ordpos[v]);
//            cout<<get(ordpos[v])<<endl;
            int dp = dep[v];
            ll re =  1;
            bug(v, tomul[v][dp-dep[v]]);
            for (int at = v; at!=-1 && dp-dep[at]<=40; at = par[at]) {
                re = re * tomul[at][dp-dep[at]]; re %= L;
            }
            cout<<re<<endl;
        }

    }

}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 26964 KB Output is correct
2 Correct 18 ms 26872 KB Output is correct
3 Correct 13 ms 26964 KB Output is correct
4 Correct 20 ms 27984 KB Output is correct
5 Correct 15 ms 27988 KB Output is correct
6 Correct 15 ms 27988 KB Output is correct
7 Correct 15 ms 27988 KB Output is correct
8 Correct 15 ms 27976 KB Output is correct
9 Correct 16 ms 26964 KB Output is correct
10 Correct 17 ms 26964 KB Output is correct
11 Correct 14 ms 26928 KB Output is correct
12 Correct 18 ms 26916 KB Output is correct
13 Correct 13 ms 26964 KB Output is correct
14 Correct 13 ms 26992 KB Output is correct
15 Correct 12 ms 26892 KB Output is correct
16 Correct 13 ms 26876 KB Output is correct
17 Correct 17 ms 26924 KB Output is correct
18 Correct 17 ms 26988 KB Output is correct
19 Correct 13 ms 26896 KB Output is correct
20 Correct 13 ms 26924 KB Output is correct
21 Correct 13 ms 26964 KB Output is correct
22 Correct 16 ms 26984 KB Output is correct
23 Correct 17 ms 26976 KB Output is correct
24 Correct 19 ms 26964 KB Output is correct
25 Correct 14 ms 26964 KB Output is correct
26 Correct 14 ms 26988 KB Output is correct
27 Correct 16 ms 26972 KB Output is correct
28 Correct 16 ms 26964 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 26976 KB Output is correct
2 Correct 984 ms 243704 KB Output is correct
3 Correct 691 ms 240860 KB Output is correct
4 Correct 920 ms 255804 KB Output is correct
5 Correct 837 ms 243352 KB Output is correct
6 Correct 675 ms 242700 KB Output is correct
7 Correct 604 ms 242684 KB Output is correct
8 Correct 448 ms 242820 KB Output is correct
9 Correct 1043 ms 265444 KB Output is correct
10 Correct 726 ms 260656 KB Output is correct
11 Correct 989 ms 245608 KB Output is correct
12 Correct 655 ms 242420 KB Output is correct
13 Correct 429 ms 242032 KB Output is correct
14 Correct 422 ms 240476 KB Output is correct
15 Correct 415 ms 240408 KB Output is correct
16 Correct 395 ms 240220 KB Output is correct
17 Correct 400 ms 241196 KB Output is correct
18 Correct 14 ms 26912 KB Output is correct
19 Correct 14 ms 26964 KB Output is correct
20 Correct 16 ms 26964 KB Output is correct
21 Correct 16 ms 26984 KB Output is correct
22 Correct 16 ms 26964 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 26976 KB Output is correct
2 Correct 984 ms 243704 KB Output is correct
3 Correct 691 ms 240860 KB Output is correct
4 Correct 920 ms 255804 KB Output is correct
5 Correct 837 ms 243352 KB Output is correct
6 Correct 675 ms 242700 KB Output is correct
7 Correct 604 ms 242684 KB Output is correct
8 Correct 448 ms 242820 KB Output is correct
9 Correct 1043 ms 265444 KB Output is correct
10 Correct 726 ms 260656 KB Output is correct
11 Correct 989 ms 245608 KB Output is correct
12 Correct 655 ms 242420 KB Output is correct
13 Correct 429 ms 242032 KB Output is correct
14 Correct 422 ms 240476 KB Output is correct
15 Correct 415 ms 240408 KB Output is correct
16 Correct 395 ms 240220 KB Output is correct
17 Correct 400 ms 241196 KB Output is correct
18 Correct 14 ms 26912 KB Output is correct
19 Correct 14 ms 26964 KB Output is correct
20 Correct 16 ms 26964 KB Output is correct
21 Correct 16 ms 26984 KB Output is correct
22 Correct 16 ms 26964 KB Output is correct
23 Correct 15 ms 26976 KB Output is correct
24 Correct 985 ms 246960 KB Output is correct
25 Correct 625 ms 241872 KB Output is correct
26 Correct 875 ms 262656 KB Output is correct
27 Correct 718 ms 243452 KB Output is correct
28 Correct 562 ms 242548 KB Output is correct
29 Correct 535 ms 242332 KB Output is correct
30 Correct 396 ms 242452 KB Output is correct
31 Correct 1072 ms 258776 KB Output is correct
32 Correct 710 ms 260176 KB Output is correct
33 Correct 938 ms 245356 KB Output is correct
34 Correct 611 ms 241816 KB Output is correct
35 Correct 14 ms 26916 KB Output is correct
36 Correct 15 ms 26964 KB Output is correct
37 Correct 14 ms 26980 KB Output is correct
38 Correct 17 ms 26964 KB Output is correct
39 Correct 14 ms 26964 KB Output is correct
40 Correct 15 ms 26964 KB Output is correct
41 Correct 14 ms 26956 KB Output is correct
42 Correct 14 ms 26964 KB Output is correct
43 Correct 16 ms 26980 KB Output is correct
44 Correct 14 ms 27000 KB Output is correct
45 Correct 14 ms 26992 KB Output is correct
46 Correct 14 ms 26964 KB Output is correct
47 Correct 14 ms 26944 KB Output is correct
48 Correct 14 ms 26976 KB Output is correct
49 Correct 15 ms 26980 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 26964 KB Output is correct
2 Correct 1097 ms 263300 KB Output is correct
3 Correct 1477 ms 261056 KB Output is correct
4 Correct 1153 ms 264168 KB Output is correct
5 Correct 947 ms 248564 KB Output is correct
6 Correct 642 ms 247640 KB Output is correct
7 Correct 507 ms 247500 KB Output is correct
8 Correct 382 ms 247728 KB Output is correct
9 Correct 1054 ms 262020 KB Output is correct
10 Correct 1518 ms 266852 KB Output is correct
11 Correct 936 ms 248424 KB Output is correct
12 Correct 1222 ms 249196 KB Output is correct
13 Correct 776 ms 247628 KB Output is correct
14 Correct 771 ms 250028 KB Output is correct
15 Correct 14 ms 26964 KB Output is correct
16 Correct 14 ms 26952 KB Output is correct
17 Correct 13 ms 26964 KB Output is correct
18 Correct 14 ms 26964 KB Output is correct
19 Correct 15 ms 26964 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 27048 KB Output is correct
2 Correct 1216 ms 258832 KB Output is correct
3 Correct 1593 ms 256488 KB Output is correct
4 Correct 1087 ms 261696 KB Output is correct
5 Correct 922 ms 250140 KB Output is correct
6 Correct 593 ms 249208 KB Output is correct
7 Correct 584 ms 248732 KB Output is correct
8 Correct 390 ms 248632 KB Output is correct
9 Correct 1132 ms 269400 KB Output is correct
10 Correct 1601 ms 267952 KB Output is correct
11 Correct 995 ms 250856 KB Output is correct
12 Correct 1219 ms 249368 KB Output is correct
13 Correct 793 ms 247660 KB Output is correct
14 Correct 804 ms 250248 KB Output is correct
15 Correct 15 ms 26964 KB Output is correct
16 Correct 14 ms 26964 KB Output is correct
17 Correct 14 ms 27000 KB Output is correct
18 Correct 15 ms 26896 KB Output is correct
19 Correct 16 ms 26984 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 26964 KB Output is correct
2 Correct 18 ms 26872 KB Output is correct
3 Correct 13 ms 26964 KB Output is correct
4 Correct 20 ms 27984 KB Output is correct
5 Correct 15 ms 27988 KB Output is correct
6 Correct 15 ms 27988 KB Output is correct
7 Correct 15 ms 27988 KB Output is correct
8 Correct 15 ms 27976 KB Output is correct
9 Correct 16 ms 26964 KB Output is correct
10 Correct 17 ms 26964 KB Output is correct
11 Correct 14 ms 26928 KB Output is correct
12 Correct 18 ms 26916 KB Output is correct
13 Correct 13 ms 26964 KB Output is correct
14 Correct 13 ms 26992 KB Output is correct
15 Correct 12 ms 26892 KB Output is correct
16 Correct 13 ms 26876 KB Output is correct
17 Correct 17 ms 26924 KB Output is correct
18 Correct 17 ms 26988 KB Output is correct
19 Correct 13 ms 26896 KB Output is correct
20 Correct 13 ms 26924 KB Output is correct
21 Correct 13 ms 26964 KB Output is correct
22 Correct 16 ms 26984 KB Output is correct
23 Correct 17 ms 26976 KB Output is correct
24 Correct 19 ms 26964 KB Output is correct
25 Correct 14 ms 26964 KB Output is correct
26 Correct 14 ms 26988 KB Output is correct
27 Correct 16 ms 26972 KB Output is correct
28 Correct 16 ms 26964 KB Output is correct
29 Correct 15 ms 26976 KB Output is correct
30 Correct 984 ms 243704 KB Output is correct
31 Correct 691 ms 240860 KB Output is correct
32 Correct 920 ms 255804 KB Output is correct
33 Correct 837 ms 243352 KB Output is correct
34 Correct 675 ms 242700 KB Output is correct
35 Correct 604 ms 242684 KB Output is correct
36 Correct 448 ms 242820 KB Output is correct
37 Correct 1043 ms 265444 KB Output is correct
38 Correct 726 ms 260656 KB Output is correct
39 Correct 989 ms 245608 KB Output is correct
40 Correct 655 ms 242420 KB Output is correct
41 Correct 429 ms 242032 KB Output is correct
42 Correct 422 ms 240476 KB Output is correct
43 Correct 415 ms 240408 KB Output is correct
44 Correct 395 ms 240220 KB Output is correct
45 Correct 400 ms 241196 KB Output is correct
46 Correct 14 ms 26912 KB Output is correct
47 Correct 14 ms 26964 KB Output is correct
48 Correct 16 ms 26964 KB Output is correct
49 Correct 16 ms 26984 KB Output is correct
50 Correct 16 ms 26964 KB Output is correct
51 Correct 15 ms 26976 KB Output is correct
52 Correct 985 ms 246960 KB Output is correct
53 Correct 625 ms 241872 KB Output is correct
54 Correct 875 ms 262656 KB Output is correct
55 Correct 718 ms 243452 KB Output is correct
56 Correct 562 ms 242548 KB Output is correct
57 Correct 535 ms 242332 KB Output is correct
58 Correct 396 ms 242452 KB Output is correct
59 Correct 1072 ms 258776 KB Output is correct
60 Correct 710 ms 260176 KB Output is correct
61 Correct 938 ms 245356 KB Output is correct
62 Correct 611 ms 241816 KB Output is correct
63 Correct 14 ms 26916 KB Output is correct
64 Correct 15 ms 26964 KB Output is correct
65 Correct 14 ms 26980 KB Output is correct
66 Correct 17 ms 26964 KB Output is correct
67 Correct 14 ms 26964 KB Output is correct
68 Correct 15 ms 26964 KB Output is correct
69 Correct 14 ms 26956 KB Output is correct
70 Correct 14 ms 26964 KB Output is correct
71 Correct 16 ms 26980 KB Output is correct
72 Correct 14 ms 27000 KB Output is correct
73 Correct 14 ms 26992 KB Output is correct
74 Correct 14 ms 26964 KB Output is correct
75 Correct 14 ms 26944 KB Output is correct
76 Correct 14 ms 26976 KB Output is correct
77 Correct 15 ms 26980 KB Output is correct
78 Correct 14 ms 26964 KB Output is correct
79 Correct 1097 ms 263300 KB Output is correct
80 Correct 1477 ms 261056 KB Output is correct
81 Correct 1153 ms 264168 KB Output is correct
82 Correct 947 ms 248564 KB Output is correct
83 Correct 642 ms 247640 KB Output is correct
84 Correct 507 ms 247500 KB Output is correct
85 Correct 382 ms 247728 KB Output is correct
86 Correct 1054 ms 262020 KB Output is correct
87 Correct 1518 ms 266852 KB Output is correct
88 Correct 936 ms 248424 KB Output is correct
89 Correct 1222 ms 249196 KB Output is correct
90 Correct 776 ms 247628 KB Output is correct
91 Correct 771 ms 250028 KB Output is correct
92 Correct 14 ms 26964 KB Output is correct
93 Correct 14 ms 26952 KB Output is correct
94 Correct 13 ms 26964 KB Output is correct
95 Correct 14 ms 26964 KB Output is correct
96 Correct 15 ms 26964 KB Output is correct
97 Correct 14 ms 27048 KB Output is correct
98 Correct 1216 ms 258832 KB Output is correct
99 Correct 1593 ms 256488 KB Output is correct
100 Correct 1087 ms 261696 KB Output is correct
101 Correct 922 ms 250140 KB Output is correct
102 Correct 593 ms 249208 KB Output is correct
103 Correct 584 ms 248732 KB Output is correct
104 Correct 390 ms 248632 KB Output is correct
105 Correct 1132 ms 269400 KB Output is correct
106 Correct 1601 ms 267952 KB Output is correct
107 Correct 995 ms 250856 KB Output is correct
108 Correct 1219 ms 249368 KB Output is correct
109 Correct 793 ms 247660 KB Output is correct
110 Correct 804 ms 250248 KB Output is correct
111 Correct 15 ms 26964 KB Output is correct
112 Correct 14 ms 26964 KB Output is correct
113 Correct 14 ms 27000 KB Output is correct
114 Correct 15 ms 26896 KB Output is correct
115 Correct 16 ms 26984 KB Output is correct
116 Correct 1155 ms 249360 KB Output is correct
117 Correct 1463 ms 251828 KB Output is correct
118 Correct 1257 ms 270348 KB Output is correct
119 Correct 952 ms 251652 KB Output is correct
120 Correct 636 ms 250120 KB Output is correct
121 Correct 605 ms 250684 KB Output is correct
122 Correct 429 ms 250704 KB Output is correct
123 Correct 1128 ms 266880 KB Output is correct
124 Correct 1509 ms 263372 KB Output is correct
125 Correct 961 ms 250548 KB Output is correct
126 Correct 1201 ms 251788 KB Output is correct
127 Correct 1173 ms 252520 KB Output is correct
128 Correct 734 ms 250492 KB Output is correct
129 Correct 816 ms 252960 KB Output is correct