oj.uz

Submission #792130

# Submission time Handle Problem Language Result Execution time Memory
792130 2023-07-24T15:41:31 Z quanlt206 Sprinkler (JOI22_sprinkler) C++14
3 / 100
 45 ms 11264 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 = 2e3 + 7;

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

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

vector<int> v[N];



struct SegmentTree {
    struct Node {
        ll lazy, val;
        Node() {
             val = 1;
        }
    } st[4 * N];
    ll mul(ll a, ll b) {
        if (b == 0) return 1;
        ll tmp = mul(a, b / 2);
        tmp = tmp * tmp % mod;
        if (b & 1) tmp = tmp * a % mod;
        return tmp;
    }
    void Up(int id, int l, int r) {
        if (l == r) return ;
        st[id].val = st[id * 2].val * st[id * 2 + 1].val % mod;
    }
    void update(int id, int l, int r, int i, ll x) {
        if (l > i || r < i) return ;
        if (l == r) {
            st[id].val = st[id].val * x % mod;
            return ;
        }
        int mid = (l + r) >> 1;
        update(id * 2, l, mid, i, x);
        update(id * 2 + 1, mid + 1, r, i, x);
        Up(id, l, r);
    }
    ll Get(int id, int l, int r, int u, int v) {
        if (l > v || r < u || l > r) return 1;
        if (u <= l && r <= v) return st[id].val;
        int mid = (l + r) >> 1;
        return Get(id * 2, l, mid, u, v) * Get(id * 2 + 1, mid + 1, r, u, v) % mod;
    }
} st[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) {
        st[d - tmp].update(1, 1, n, 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;
//    ans = ans * res2[x][0] % mod;
    FOR(i, 0, 40) ans = ans * res[x][i] % mod;
    x = P[x];
//    cout<<res[2][1]<<"\n";
//    cout <<x<<" "<<ans<<"\n";
    while (x != -1 && tmp <= 40) {
        ans = ans * res2[x][tmp] % mod;
//        cout<<x<<" "<<ans<<"\n";
//        ans = ans * res[x][0] % mod;
        if (tmp < 40) {
            int t = lower_bound(all(v[x]), last_x) - v[x].begin();
            if (t < (int)v[x].size()) {
                FOR(j, tmp + 1, 40) {
                    ans = ans * st[j].Get(1, 1, n, pos[v[x][0]], pos[v[x][t]] - 1) % mod;
                    ans = ans * st[j].Get(1, 1, n, pos[v[x][t]] + 1, pos[v[x].back()]) % mod;
                }
            }
//            for (auto y : v[x])
//                if (y != last_x && y != P[x]) {
//                    FOR(j, 0, 40)
//                        if (j >= tmp + 1) {
//                            ans = ans * res[y][j] % mod;
////                            cout<<y<<" "<<j<<" "<<res[y][j]<<"\n";
//                        }
//                }
        }
//        cout<<x<<" "<<ans<<"\n";
//        break;
        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]));
    }
    int cnt = 0;
    FOR(i, 1, n)
        for (auto x : v[i]) pos[x] = ++cnt;
    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 3 ms 5588 KB Output is correct
2 Correct 3 ms 5588 KB Output is correct
3 Correct 2 ms 5588 KB Output is correct
4 Correct 45 ms 6508 KB Output is correct
5 Correct 45 ms 6508 KB Output is correct
6 Correct 24 ms 6528 KB Output is correct
7 Correct 20 ms 6532 KB Output is correct
8 Correct 9 ms 6484 KB Output is correct
9 Correct 3 ms 5664 KB Output is correct
10 Correct 3 ms 5660 KB Output is correct
11 Correct 4 ms 5588 KB Output is correct
12 Correct 6 ms 5588 KB Output is correct
13 Correct 5 ms 5588 KB Output is correct
14 Correct 3 ms 5588 KB Output is correct
15 Correct 3 ms 5660 KB Output is correct
16 Correct 4 ms 5588 KB Output is correct
17 Correct 5 ms 5588 KB Output is correct
18 Correct 8 ms 5588 KB Output is correct
19 Correct 4 ms 5588 KB Output is correct
20 Correct 4 ms 5588 KB Output is correct
21 Correct 4 ms 5588 KB Output is correct
22 Correct 6 ms 5716 KB Output is correct
23 Correct 6 ms 5660 KB Output is correct
24 Correct 3 ms 5588 KB Output is correct
25 Correct 3 ms 5656 KB Output is correct
26 Correct 4 ms 5588 KB Output is correct
27 Correct 5 ms 5656 KB Output is correct
28 Correct 5 ms 5656 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5588 KB Output is correct
2 Runtime error 7 ms 11220 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5588 KB Output is correct
2 Runtime error 7 ms 11220 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5588 KB Output is correct
2 Runtime error 8 ms 11188 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5588 KB Output is correct
2 Runtime error 7 ms 11264 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5588 KB Output is correct
2 Correct 3 ms 5588 KB Output is correct
3 Correct 2 ms 5588 KB Output is correct
4 Correct 45 ms 6508 KB Output is correct
5 Correct 45 ms 6508 KB Output is correct
6 Correct 24 ms 6528 KB Output is correct
7 Correct 20 ms 6532 KB Output is correct
8 Correct 9 ms 6484 KB Output is correct
9 Correct 3 ms 5664 KB Output is correct
10 Correct 3 ms 5660 KB Output is correct
11 Correct 4 ms 5588 KB Output is correct
12 Correct 6 ms 5588 KB Output is correct
13 Correct 5 ms 5588 KB Output is correct
14 Correct 3 ms 5588 KB Output is correct
15 Correct 3 ms 5660 KB Output is correct
16 Correct 4 ms 5588 KB Output is correct
17 Correct 5 ms 5588 KB Output is correct
18 Correct 8 ms 5588 KB Output is correct
19 Correct 4 ms 5588 KB Output is correct
20 Correct 4 ms 5588 KB Output is correct
21 Correct 4 ms 5588 KB Output is correct
22 Correct 6 ms 5716 KB Output is correct
23 Correct 6 ms 5660 KB Output is correct
24 Correct 3 ms 5588 KB Output is correct
25 Correct 3 ms 5656 KB Output is correct
26 Correct 4 ms 5588 KB Output is correct
27 Correct 5 ms 5656 KB Output is correct
28 Correct 5 ms 5656 KB Output is correct
29 Correct 2 ms 5588 KB Output is correct
30 Runtime error 7 ms 11220 KB Execution killed with signal 11
31 Halted 0 ms 0 KB -