oj.uz

Submission #792161

# Submission time Handle Problem Language Result Execution time Memory
792161 2023-07-24T16:41:27 Z quanlt206 Sprinkler (JOI22_sprinkler) C++14
3 / 100
 4000 ms 729400 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 117 ms 267984 KB Output is correct
2 Correct 111 ms 268128 KB Output is correct
3 Correct 108 ms 267956 KB Output is correct
4 Correct 112 ms 270136 KB Output is correct
5 Correct 114 ms 270300 KB Output is correct
6 Correct 132 ms 270416 KB Output is correct
7 Correct 113 ms 270412 KB Output is correct
8 Correct 116 ms 270464 KB Output is correct
9 Correct 109 ms 268060 KB Output is correct
10 Correct 113 ms 268020 KB Output is correct
11 Correct 109 ms 268100 KB Output is correct
12 Correct 110 ms 268064 KB Output is correct
13 Correct 109 ms 268076 KB Output is correct
14 Correct 110 ms 267980 KB Output is correct
15 Correct 108 ms 267984 KB Output is correct
16 Correct 111 ms 268044 KB Output is correct
17 Correct 109 ms 268088 KB Output is correct
18 Correct 109 ms 268116 KB Output is correct
19 Correct 107 ms 267992 KB Output is correct
20 Correct 109 ms 268060 KB Output is correct
21 Correct 124 ms 268092 KB Output is correct
22 Correct 108 ms 268076 KB Output is correct
23 Correct 110 ms 268100 KB Output is correct
24 Correct 110 ms 267984 KB Output is correct
25 Correct 108 ms 268072 KB Output is correct
26 Correct 111 ms 267988 KB Output is correct
27 Correct 114 ms 268084 KB Output is correct
28 Correct 108 ms 268024 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 268032 KB Output is correct
2 Execution timed out 4091 ms 729400 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 268032 KB Output is correct
2 Execution timed out 4091 ms 729400 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 267972 KB Output is correct
2 Execution timed out 4067 ms 696116 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

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

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 267984 KB Output is correct
2 Correct 111 ms 268128 KB Output is correct
3 Correct 108 ms 267956 KB Output is correct
4 Correct 112 ms 270136 KB Output is correct
5 Correct 114 ms 270300 KB Output is correct
6 Correct 132 ms 270416 KB Output is correct
7 Correct 113 ms 270412 KB Output is correct
8 Correct 116 ms 270464 KB Output is correct
9 Correct 109 ms 268060 KB Output is correct
10 Correct 113 ms 268020 KB Output is correct
11 Correct 109 ms 268100 KB Output is correct
12 Correct 110 ms 268064 KB Output is correct
13 Correct 109 ms 268076 KB Output is correct
14 Correct 110 ms 267980 KB Output is correct
15 Correct 108 ms 267984 KB Output is correct
16 Correct 111 ms 268044 KB Output is correct
17 Correct 109 ms 268088 KB Output is correct
18 Correct 109 ms 268116 KB Output is correct
19 Correct 107 ms 267992 KB Output is correct
20 Correct 109 ms 268060 KB Output is correct
21 Correct 124 ms 268092 KB Output is correct
22 Correct 108 ms 268076 KB Output is correct
23 Correct 110 ms 268100 KB Output is correct
24 Correct 110 ms 267984 KB Output is correct
25 Correct 108 ms 268072 KB Output is correct
26 Correct 111 ms 267988 KB Output is correct
27 Correct 114 ms 268084 KB Output is correct
28 Correct 108 ms 268024 KB Output is correct
29 Correct 109 ms 268032 KB Output is correct
30 Execution timed out 4091 ms 729400 KB Time limit exceeded
31 Halted 0 ms 0 KB -