oj.uz

Submission #588766

# Submission time Handle Problem Language Result Execution time Memory
588766 2022-07-04T04:13:33 Z balbit Sprinkler (JOI22_sprinkler) C++14
9 / 100
 4000 ms 99628 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);
}

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 findrng(int v, int tdp) {
    int l,r;
    {
        int at = v;
        while (dep[at] < tdp) {
            if (SZ(g[at]) == 0) {
                return {-1, -1};
            }
            at = g[at][0];
        }
        l = ordpos[at];
    }
    {
        int at = v;
        while (dep[at] < tdp) at = g[at].back();
        r = ordpos[at];
    }
    return {l,r};
}

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();
    REP(i,n) cin>>H[i], MO(ordpos[i],ordpos[i],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 = findrng(at, dp);
                if (ha.f == -1) continue;
                bug(ha.f, ha.s, w);
                MO(ha.f, ha.s, w);
            }
        }else{
            int v; cin>>v; --v;
            bug(ordpos[v]);
            cout<<get(ordpos[v])<<endl;
        }

    }

}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 26844 KB Output is correct
2 Correct 13 ms 26844 KB Output is correct
3 Correct 14 ms 26952 KB Output is correct
4 Correct 21 ms 27188 KB Output is correct
5 Runtime error 33 ms 54612 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 26964 KB Output is correct
2 Correct 485 ms 58760 KB Output is correct
3 Correct 876 ms 59388 KB Output is correct
4 Correct 678 ms 71840 KB Output is correct
5 Correct 649 ms 59228 KB Output is correct
6 Correct 604 ms 57520 KB Output is correct
7 Correct 604 ms 57968 KB Output is correct
8 Correct 469 ms 58120 KB Output is correct
9 Correct 532 ms 78676 KB Output is correct
10 Correct 977 ms 77344 KB Output is correct
11 Correct 534 ms 58656 KB Output is correct
12 Correct 903 ms 59324 KB Output is correct
13 Correct 897 ms 58736 KB Output is correct
14 Correct 912 ms 57764 KB Output is correct
15 Correct 864 ms 56816 KB Output is correct
16 Correct 768 ms 57088 KB Output is correct
17 Correct 872 ms 57944 KB Output is correct
18 Correct 13 ms 26964 KB Output is correct
19 Correct 13 ms 26928 KB Output is correct
20 Correct 15 ms 26964 KB Output is correct
21 Correct 14 ms 26964 KB Output is correct
22 Correct 14 ms 26904 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 26964 KB Output is correct
2 Correct 485 ms 58760 KB Output is correct
3 Correct 876 ms 59388 KB Output is correct
4 Correct 678 ms 71840 KB Output is correct
5 Correct 649 ms 59228 KB Output is correct
6 Correct 604 ms 57520 KB Output is correct
7 Correct 604 ms 57968 KB Output is correct
8 Correct 469 ms 58120 KB Output is correct
9 Correct 532 ms 78676 KB Output is correct
10 Correct 977 ms 77344 KB Output is correct
11 Correct 534 ms 58656 KB Output is correct
12 Correct 903 ms 59324 KB Output is correct
13 Correct 897 ms 58736 KB Output is correct
14 Correct 912 ms 57764 KB Output is correct
15 Correct 864 ms 56816 KB Output is correct
16 Correct 768 ms 57088 KB Output is correct
17 Correct 872 ms 57944 KB Output is correct
18 Correct 13 ms 26964 KB Output is correct
19 Correct 13 ms 26928 KB Output is correct
20 Correct 15 ms 26964 KB Output is correct
21 Correct 14 ms 26964 KB Output is correct
22 Correct 14 ms 26904 KB Output is correct
23 Correct 12 ms 26964 KB Output is correct
24 Runtime error 281 ms 99628 KB Execution killed with signal 11
25 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 26964 KB Output is correct
2 Correct 2379 ms 75636 KB Output is correct
3 Execution timed out 4062 ms 67204 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 26964 KB Output is correct
2 Correct 2436 ms 71156 KB Output is correct
3 Execution timed out 4067 ms 62608 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 26844 KB Output is correct
2 Correct 13 ms 26844 KB Output is correct
3 Correct 14 ms 26952 KB Output is correct
4 Correct 21 ms 27188 KB Output is correct
5 Runtime error 33 ms 54612 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -