oj.uz

Submission #792162

# Submission time Handle Problem Language Result Execution time Memory
792162 2023-07-24T16:42:04 Z quanlt206 Sprinkler (JOI22_sprinkler) C++17
3 / 100
 4000 ms 729188 KB 
#include<bits/stdc++.h>
#define X first
#define Y second
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, b, a) for (int i = (b); i >= (a); i--)
#define REP(i, a, b) for (int i = (a); i < (b); i++)
#define MASK(x) (1LL << (x))
#define all(x) begin(x), end(x)

using namespace std;

typedef long long ll;
typedef long double ld;
typedef double db;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
typedef pair<ll, int> pli;
typedef pair<ll, pii> plii;

template<class A, class B>
    bool maximize(A& x, B y) {
        if (x < y) return x = y, true; else return false;
    }
template<class A, class B>
    bool minimize(A& x, B y) {
        if (x > y) return x = y, true; else return false;
    }
/* END OF TEMPLATE */

const int N = 2e5 + 7;

int n, mod, P[N], pos[N];

ll res[N][50], h[N], res2[N][50];

vector<int> v[N];



struct SegmentTree {
    int n;  // array size
    vector<int> t;
    SegmentTree() {
        n = 0;
    }
    void build(int n) {  // build the tree
        this->n = n;
        t.resize(2 * n + 3);
        for (auto &x : t) x = 1;
    }

    void update(int p, int value) {  // set value at position p
        p+=n;
        for (t[p] = 1LL * t[p] * value % mod; p > 1; p >>= 1) {
            t[p>>1] = 1LL * t[p] * t[p^1] % mod;
        }
    }
    ll Get(int l, int r) {  // sum on interval [l, r)
        if (l >= r) return 1;
        ll res = 1;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l&1) res = 1LL * res * t[l++] % mod;
            if (r&1) res = 1LL * res * t[--r] % mod;
        }
        return res;
    }
} st[N][42];

void dfs(int x, int par) {
    P[x] = par;
    for (auto y : v[x])
        if (y != par) dfs(y, x);
}

void firstQuery() {
    int x, d, w;
    cin>>x>>d>>w;
    FOR(j, 0, d) res2[x][j] = res2[x][j] * w % mod;
    int tmp = 0;
    while (x != -1 && tmp <= d) {
        if (x != 1) st[P[x]][d - tmp].update(pos[x], w);
        res[x][d - tmp] = res[x][d - tmp] * w % mod;
        tmp++;
        x = P[x];
    }
}

void secondQuery() {
    int x;
    cin>>x;
    ll ans = h[x];
    int tmp = 1;
    int last_x = x;
    FOR(i, 0, 40) ans = ans * res[x][i] % mod;
    x = P[x];
//    cout<<x<<" "<<ans<<"\n";
    while (x != -1 && tmp <= 40) {
        ans = ans * res2[x][tmp] % mod;
        if (tmp < 40) {
            int t = pos[last_x];
            FOR(j, tmp + 1, 40) {
                ans = ans * st[x][j].Get(0, t - 1 + 1) % mod;
//                cout<<0<<" "<<t<<"\n";
//                cout<<j<<" "<<ans<<"\n";
                ans = ans * st[x][j].Get(t + 1, (int)v[x].size()) % mod;
//                exit(0);
            }
        }
        last_x = x;
        x = P[x];
        tmp++;
    }
    cout<<ans<<"\n";
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>mod;
    REP(i, 1, n) {
        int x, y;
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    FOR(i, 1, n)
        FOR(j, 0, 40) res[i][j] = res2[i][j] = 1;
    FOR(i, 1, n) cin>>h[i];
    dfs(1, -1);
    FOR(i, 1, n) {
        vector<int> a;
        for (auto x : v[i])
            if (x != P[i]) a.push_back(x);
        v[i] = a;
        sort(all(v[i]));
        REP(j, 0, (int)v[i].size()) pos[v[i][j]] = j;
        FOR(j, 0, 40) st[i][j].build((int)v[i].size());
    }
    int Q;
    cin>>Q;
    while (Q--) {
        int type;
        cin>>type;
        if (type == 1) firstQuery(); else secondQuery();
    }
    return 0;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 267964 KB Output is correct
2 Correct 114 ms 267976 KB Output is correct
3 Correct 117 ms 268172 KB Output is correct
4 Correct 117 ms 270156 KB Output is correct
5 Correct 119 ms 270356 KB Output is correct
6 Correct 117 ms 270416 KB Output is correct
7 Correct 119 ms 270444 KB Output is correct
8 Correct 117 ms 270424 KB Output is correct
9 Correct 112 ms 268036 KB Output is correct
10 Correct 111 ms 267988 KB Output is correct
11 Correct 168 ms 267980 KB Output is correct
12 Correct 113 ms 268024 KB Output is correct
13 Correct 113 ms 268104 KB Output is correct
14 Correct 115 ms 268064 KB Output is correct
15 Correct 115 ms 268016 KB Output is correct
16 Correct 114 ms 268096 KB Output is correct
17 Correct 115 ms 268064 KB Output is correct
18 Correct 115 ms 267988 KB Output is correct
19 Correct 115 ms 267964 KB Output is correct
20 Correct 115 ms 268024 KB Output is correct
21 Correct 115 ms 268024 KB Output is correct
22 Correct 112 ms 268072 KB Output is correct
23 Correct 126 ms 268116 KB Output is correct
24 Correct 114 ms 268072 KB Output is correct
25 Correct 113 ms 267980 KB Output is correct
26 Correct 114 ms 268024 KB Output is correct
27 Correct 114 ms 268004 KB Output is correct
28 Correct 116 ms 268036 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 268008 KB Output is correct
2 Execution timed out 4096 ms 729188 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 268008 KB Output is correct
2 Execution timed out 4096 ms 729188 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 267976 KB Output is correct
2 Execution timed out 4033 ms 695820 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 268028 KB Output is correct
2 Execution timed out 4005 ms 697124 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 267964 KB Output is correct
2 Correct 114 ms 267976 KB Output is correct
3 Correct 117 ms 268172 KB Output is correct
4 Correct 117 ms 270156 KB Output is correct
5 Correct 119 ms 270356 KB Output is correct
6 Correct 117 ms 270416 KB Output is correct
7 Correct 119 ms 270444 KB Output is correct
8 Correct 117 ms 270424 KB Output is correct
9 Correct 112 ms 268036 KB Output is correct
10 Correct 111 ms 267988 KB Output is correct
11 Correct 168 ms 267980 KB Output is correct
12 Correct 113 ms 268024 KB Output is correct
13 Correct 113 ms 268104 KB Output is correct
14 Correct 115 ms 268064 KB Output is correct
15 Correct 115 ms 268016 KB Output is correct
16 Correct 114 ms 268096 KB Output is correct
17 Correct 115 ms 268064 KB Output is correct
18 Correct 115 ms 267988 KB Output is correct
19 Correct 115 ms 267964 KB Output is correct
20 Correct 115 ms 268024 KB Output is correct
21 Correct 115 ms 268024 KB Output is correct
22 Correct 112 ms 268072 KB Output is correct
23 Correct 126 ms 268116 KB Output is correct
24 Correct 114 ms 268072 KB Output is correct
25 Correct 113 ms 267980 KB Output is correct
26 Correct 114 ms 268024 KB Output is correct
27 Correct 114 ms 268004 KB Output is correct
28 Correct 116 ms 268036 KB Output is correct
29 Correct 113 ms 268008 KB Output is correct
30 Execution timed out 4096 ms 729188 KB Time limit exceeded
31 Halted 0 ms 0 KB -