oj.uz

Submission #892281

# Submission time Handle Problem Language Result Execution time Memory
892281 2023-12-25T06:41:37 Z vjudge1 Sprinkler (JOI22_sprinkler) C++17
9 / 100
 1133 ms 64196 KB 
#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
#define int long long

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}

const int N = 2e5 + 1;

int L, n;

struct SegTree{
    int T[N * 4], lazy[N * 4];
    SegTree(){
        for ( int i = 0; i < N * 4; i++ ){
            T[i] = lazy[i] = 1;
        }
    }
    void push(int v, int l, int r){
        if ( l != r ){
            lazy[v * 2] = lazy[v * 2] * lazy[v] % L;
            lazy[v * 2 + 1] = lazy[v * 2 + 1] * lazy[v] % L;
        }
        T[v] = T[v] * lazy[v] % L;
        lazy[v] = 1;
    }
    void upd(int v, int l, int r, int tl, int tr, int val){
        if ( tl > r or tr < l ){
            return;
        }
        push(v, l, r);
        if ( tl <= l && tr >= r ){
            lazy[v] = lazy[v] * val % L;
            push(v, l, r);
            return;
        }
        int md = (l + r) >> 1;
        upd(v * 2 + 1, md + 1, r, tl, tr, val);
        upd(v * 2, l, md, tl, tr, val);
        T[v] = (T[v * 2] * T[v * 2 + 1]) % L;
    };
    void upd(int l, int r, int val){
        upd(1, 0, n - 1, l, r, val);
    }
    int get(int v, int l, int r, int tl, int tr){
        push(v, l, r);
        if ( l > tr or r < tl ){
            return 1;
        }
        if ( tl <= l && tr >= r ){
            return T[v];
        }
        int md = (l + r) >> 1;
        return (get(v * 2, l, md, tl, tr) * get(v * 2 + 1, md + 1, r, tl, tr)) % L;
    }
    int get(int l, int r){
        return get(1, 0, n - 1, l, r);
    }
} seg;

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> L;
    vector <vector<int>> G(n);
    for ( int i = 0; i + 1 < n; i++ ){
        int u, v; cin >> u >> v;
        --u, --v;
        G[u].pb(v), G[v].pb(u);
    }
    vector <int> h(n);
    for ( auto &u: h ) cin >> u;
    int q; cin >> q;
    vector <ar<int,4>> Q(q);
    bool Qflag = true;
    for ( auto &[t, x, d, w]: Q ){
        cin >> t >> x;
        --x;
        if ( t == 1 ){
            cin >> d >> w;
            Qflag &= (d <= 2);
        }
    }
    if ( false && min(n, q) <= 1000 ){ // subtask #1
        for ( auto &[t, x, d, w]: Q ){
            if ( t == 1 ){
                auto dfs = [&](auto dfs, int u, int p, int D) -> void{
                    h[u] = h[u] * w % L;
                    if ( D != d ){
                        for ( auto &v: G[u] ){
                            if ( v != p ){
                                dfs(dfs, v, u, D + 1);
                            }
                        }
                    }
                };
                dfs(dfs, x, -1, 0);
            } else cout << h[x] << ln;
        }
        return 0;
    }
    if ( Qflag ){ // subtask #2, 3
        vector <int> fa(n), id(n);
        vector <ar<int,2>> ch(n, {-1, -1});
        int ct = 0;
        auto dfs = [&](auto dfs, int u, int p) -> void{
            fa[u] = p;
            for ( auto &v: G[u] ){
                if ( v != p ){
                    id[v] = ++ct;
                    if ( ch[u][0] == -1 ){
                        ch[u][0] = v;
                    } ch[u][1] = v;
                }
            }
            for ( auto &v: G[u] ){
                if ( v != p ){
                    dfs(dfs, v, u);
                }
            }
        };
        dfs(dfs, 0, -1);
        for ( int i = 0; i < n; i++ ){
            seg.upd(id[i], id[i], h[i]);
        }
        for ( auto &[t, x, d, w]: Q ){
            if ( t == 1 ){
                seg.upd(id[x], id[x], w);
                if ( d > 0 ){
                    if ( fa[x] != -1 ){
                        seg.upd(id[fa[x]], id[fa[x]], w);
                    }
                    if ( ch[x][0] != -1 ){
                        seg.upd(id[ch[x][0]], id[ch[x][1]], w);
                    }
                }
            } else{
                cout << seg.get(id[x], id[x]) << ln;
            }
        }
    }

    cout << '\n';
}

/*
4 7
1 2
2 3
3 4
1
1
1
1
6
1 2 1 2
1 1 0 2
2 1
2 2
2 3
2 4
*/

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 12892 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 523 ms 57088 KB Output is correct
3 Correct 751 ms 57812 KB Output is correct
4 Correct 612 ms 61576 KB Output is correct
5 Correct 616 ms 57296 KB Output is correct
6 Correct 584 ms 56972 KB Output is correct
7 Correct 609 ms 57584 KB Output is correct
8 Correct 497 ms 57812 KB Output is correct
9 Correct 531 ms 63992 KB Output is correct
10 Correct 818 ms 64196 KB Output is correct
11 Correct 578 ms 56912 KB Output is correct
12 Correct 767 ms 57476 KB Output is correct
13 Correct 1133 ms 57932 KB Output is correct
14 Correct 1101 ms 58320 KB Output is correct
15 Correct 947 ms 57452 KB Output is correct
16 Correct 938 ms 58192 KB Output is correct
17 Correct 937 ms 58548 KB Output is correct
18 Correct 2 ms 12892 KB Output is correct
19 Correct 3 ms 12900 KB Output is correct
20 Correct 3 ms 12892 KB Output is correct
21 Correct 3 ms 12892 KB Output is correct
22 Correct 3 ms 12892 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 523 ms 57088 KB Output is correct
3 Correct 751 ms 57812 KB Output is correct
4 Correct 612 ms 61576 KB Output is correct
5 Correct 616 ms 57296 KB Output is correct
6 Correct 584 ms 56972 KB Output is correct
7 Correct 609 ms 57584 KB Output is correct
8 Correct 497 ms 57812 KB Output is correct
9 Correct 531 ms 63992 KB Output is correct
10 Correct 818 ms 64196 KB Output is correct
11 Correct 578 ms 56912 KB Output is correct
12 Correct 767 ms 57476 KB Output is correct
13 Correct 1133 ms 57932 KB Output is correct
14 Correct 1101 ms 58320 KB Output is correct
15 Correct 947 ms 57452 KB Output is correct
16 Correct 938 ms 58192 KB Output is correct
17 Correct 937 ms 58548 KB Output is correct
18 Correct 2 ms 12892 KB Output is correct
19 Correct 3 ms 12900 KB Output is correct
20 Correct 3 ms 12892 KB Output is correct
21 Correct 3 ms 12892 KB Output is correct
22 Correct 3 ms 12892 KB Output is correct
23 Correct 2 ms 12892 KB Output is correct
24 Incorrect 492 ms 57028 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Incorrect 138 ms 45948 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 12892 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 12892 KB Output isn't correct
2 Halted 0 ms 0 KB -