oj.uz

Submission #792132

# Submission time Handle Problem Language Result Execution time Memory
792132 2023-07-24T15:42:05 Z quanlt206 Sprinkler (JOI22_sprinkler) C++14
3 / 100
 4000 ms 702020 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 {
    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 220 ms 531012 KB Output is correct
2 Correct 177 ms 531048 KB Output is correct
3 Correct 250 ms 530960 KB Output is correct
4 Correct 257 ms 531888 KB Output is correct
5 Correct 253 ms 531916 KB Output is correct
6 Correct 215 ms 531844 KB Output is correct
7 Correct 207 ms 531820 KB Output is correct
8 Correct 187 ms 531944 KB Output is correct
9 Correct 208 ms 531012 KB Output is correct
10 Correct 182 ms 531020 KB Output is correct
11 Correct 179 ms 531084 KB Output is correct
12 Correct 186 ms 531056 KB Output is correct
13 Correct 184 ms 531000 KB Output is correct
14 Correct 179 ms 531092 KB Output is correct
15 Correct 181 ms 530976 KB Output is correct
16 Correct 184 ms 531040 KB Output is correct
17 Correct 185 ms 530996 KB Output is correct
18 Correct 188 ms 531092 KB Output is correct
19 Correct 183 ms 531020 KB Output is correct
20 Correct 181 ms 531084 KB Output is correct
21 Correct 184 ms 531016 KB Output is correct
22 Correct 185 ms 531032 KB Output is correct
23 Correct 190 ms 531088 KB Output is correct
24 Correct 180 ms 531084 KB Output is correct
25 Correct 179 ms 531052 KB Output is correct
26 Correct 180 ms 531016 KB Output is correct
27 Correct 201 ms 531020 KB Output is correct
28 Correct 193 ms 530988 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 531020 KB Output is correct
2 Execution timed out 4105 ms 697516 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 531020 KB Output is correct
2 Execution timed out 4105 ms 697516 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 530980 KB Output is correct
2 Execution timed out 4100 ms 702020 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 531056 KB Output is correct
2 Execution timed out 4144 ms 700724 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 531012 KB Output is correct
2 Correct 177 ms 531048 KB Output is correct
3 Correct 250 ms 530960 KB Output is correct
4 Correct 257 ms 531888 KB Output is correct
5 Correct 253 ms 531916 KB Output is correct
6 Correct 215 ms 531844 KB Output is correct
7 Correct 207 ms 531820 KB Output is correct
8 Correct 187 ms 531944 KB Output is correct
9 Correct 208 ms 531012 KB Output is correct
10 Correct 182 ms 531020 KB Output is correct
11 Correct 179 ms 531084 KB Output is correct
12 Correct 186 ms 531056 KB Output is correct
13 Correct 184 ms 531000 KB Output is correct
14 Correct 179 ms 531092 KB Output is correct
15 Correct 181 ms 530976 KB Output is correct
16 Correct 184 ms 531040 KB Output is correct
17 Correct 185 ms 530996 KB Output is correct
18 Correct 188 ms 531092 KB Output is correct
19 Correct 183 ms 531020 KB Output is correct
20 Correct 181 ms 531084 KB Output is correct
21 Correct 184 ms 531016 KB Output is correct
22 Correct 185 ms 531032 KB Output is correct
23 Correct 190 ms 531088 KB Output is correct
24 Correct 180 ms 531084 KB Output is correct
25 Correct 179 ms 531052 KB Output is correct
26 Correct 180 ms 531016 KB Output is correct
27 Correct 201 ms 531020 KB Output is correct
28 Correct 193 ms 530988 KB Output is correct
29 Correct 181 ms 531020 KB Output is correct
30 Execution timed out 4105 ms 697516 KB Time limit exceeded
31 Halted 0 ms 0 KB -