oj.uz

답안 #850782

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
850782 2023-09-17T12:39:28 Z EJIC_B_KEDAX Sprinkler (JOI22_sprinkler) C++14
9 / 100
 4000 ms 276384 KB 
#include <bits/stdc++.h>
#include <random>

#ifndef LOCAL
//    #pragma GCC optimize("O3")
//    #pragma GCC optimize("Ofast")
//    #pragma GCC optimize("unroll-loops")
//    #pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt")
#endif
using namespace std;
typedef long long ll;
typedef double dd;
typedef long double ld;
typedef unsigned int uii;
#define x first
#define y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()



void solve();

mt19937_64 mt(1);

int32_t main() {
#ifdef LOCAL
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
#else
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    //freopen("amusing.in", "r", stdin);
    //freopen("amusing.out", "w", stdout);
#endif
    cout << fixed << setprecision(30);
    int tests = 1;
    //cin >> tests;
    while (tests--) {
        solve();
    }
}

#define int ll

ll mod;

class SegmentTree {
public:
    void build(const vector<int>& b) {
        int sz = 1;
        while (sz < b.size()) {
            sz *= 2;
        }
        x.resize(2 * sz - 1);
        vn.resize(2 * sz - 1, 1);
        size = 2 * sz - 1;
        for (int i = sz - 1; i < 2 * sz - 1; i++) {
            if (i - sz + 1 < b.size()) {
                x[i] = b[i - sz + 1];
            } else {
                x[i] = 0;
            }
        }
        for (int i = sz - 2; i >= 0; i--) {
            //update(i);
            x[i] = 0;
        }
    }

    int get(int l, int r, int i = 0, int lx = 0, int rx = -1) {
        if (rx == -1) {
            rx = size / 2;
        }
        if (lx > r || rx < l) {
            return 0;
        }

        if (lx >= l && rx <= r) {
            return x[i];
        }

        updateVN(i);
        return get(l, r, 2 * i + 1, lx, (rx + lx) / 2) + get(l, r, 2 * i + 2, (rx + lx) / 2 + 1, rx);
    }

    void change(int ind, int c, int i = 0, int lx = 0, int rx = -1) {
        if (rx == -1) {
            rx = size / 2;
        }
        if (lx == rx) {
            x[i] = c;
            return;
        }
        updateVN(i);
        if ((rx + lx) / 2 >= ind) {
            change(ind, c, 2 * i + 1, lx, (rx + lx) / 2);
        } else {
            change(ind, c, 2 * i + 2, (rx + lx) / 2 + 1, rx);
        }
        //update(i);
    }
    void plusOtr(int l, int r, ll p, int i = 0, int lx = 0, int rx = -1) {
        if (r < l) {
            return;
        }
        if (rx == -1) {
            rx = size / 2;
        }
        if (lx >= l && rx <= r) {
            x[i] = (x[i] * p) % mod;
            vn[i] = (vn[i] * p) % mod;
            return;
        }
        if (lx > r || rx < l) {
            return;
        }
        updateVN(i);
        plusOtr(l, r, p, 2 * i + 1, lx, (rx + lx) / 2);
        plusOtr(l, r, p, 2 * i + 2, (rx + lx) / 2 + 1, rx);
        //update(i);
    }
private:
    vector<ll> x, vn;
    int size;
    void updateVN(int i) {
        if (2 * i + 2 < size) {
            if (vn[i] != 1) {
                if (x[2 * i + 1]) {
                    x[2 * i + 1] = (x[2 * i + 1] * vn[i]) % mod;
                }
                vn[2 * i + 1] = (vn[2 * i + 1] * vn[i]) % mod;
                if (x[2 * i + 2]) {
                    x[2 * i + 2] = (x[2 * i + 2] * vn[i]) % mod;
                }
                vn[2 * i + 2] = (vn[2 * i + 2] * vn[i]) % mod;
                vn[i] = 1;
            }
        }
    }
    void update(int i) {
        if (2 * i + 2 < size) {
            x[i] = x[2 * i + 1] + x[2 * i + 2];
        }
    }
};

void dfs(int s, int p, vector<vector<int>>& g, vector<int>& dist, vector<vector<int>>& d, vector<vector<pair<int, int>>>& seg, vector<int>& pr) {
    if (p != -1) {
        dist[s] = dist[p] + 1;
    } else {
        dist[s] = 0;
    }
    pr[s] = p;
    d[dist[s]].push_back(s);
    seg[s][0] = {d[dist[s]].size() - 1, d[dist[s]].size() - 1};
    for (int i = 1; i < 41; i++) {
        seg[s][i].x = INT32_MAX;
    }
    vector<int> l(41, INT32_MIN);
    bool f = true;
    for (int i : g[s]) {
        if (i != p) {
            dfs(i, s, g, dist, d, seg, pr);
            if (f) {
                f = false;
                for (int j = 1; j < 41; j++) {
                    seg[s][j].x = seg[i][j - 1].x;
                }
            }
            for (int j = 1; j < 41; j++) {
                l[j] = seg[i][j - 1].y;
            }
        }
    }
    for (int j = 1; j < 41; j++) {
        seg[s][j].y = l[j];
    }
}

void solve() {
    int n;
    cin >> n >> mod;
    vector<vector<int>> g(n), d(n);
    vector<int> deg(n, 0), dist(n), h(n), p(n);
    vector<vector<pair<int, int>>> seg(n, vector<pair<int, int>>(41, {INT32_MAX, INT32_MIN}));
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v; u--; v--;
        g[u].push_back(v);
        g[v].push_back(u);
        deg[u]++;
        deg[v]++;
    }
    int root = 0;
    for (int i = 0; i < n; i++) {
        if (deg[i] == 1) {
            root = i;
            break;
        }
    }
    dfs(root, -1, g, dist, d, seg, p);
    for (int i = 0; i < n; i++) {
        cin >> h[i];
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < d[i].size(); j++) {
            d[i][j] = h[d[i][j]];
        }
    }
    vector<SegmentTree> dec(n);
    for (int i = 0; i < n; i++) {
        dec[i].build(d[i]);
    }
    int q;
    cin >> q;
    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int x, dk, wk;
            cin >> x >> dk >> wk; x--;
            for (int l = -dk; l <= dk; l++) {
                if (dist[x] - l < 0) {
                    break;
                }
                if (dist[x] - l >= n) {
                    continue;
                }
                int l1 = INT32_MAX, r1 = INT32_MIN, nw = x;
                for (int i = 0; i <= dk && nw >= 0 && 2 * i - l <= dk; i++) {
                    if (i - l < 0) {
                        nw = p[nw];
                        continue;
                    }
                    l1 = min(l1, seg[nw][i - l].x);
                    r1 = max(r1, seg[nw][i - l].y);
                    nw = p[nw];
                }
                dec[dist[x] - l].plusOtr(l1, r1, wk);
            }
        } else {
            int x;
            cin >> x; x--;
            cout << (dec[dist[x]].get(seg[x][0].x, seg[x][0].y) % mod + mod) % mod << '\n';
        }
    }
}

Compilation message

sprinkler.cpp: In member function 'void SegmentTree::build(const std::vector<long long int>&)':
sprinkler.cpp:52:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         while (sz < b.size()) {
      |                ~~~^~~~~~~~~~
sprinkler.cpp:59:28: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |             if (i - sz + 1 < b.size()) {
      |                 ~~~~~~~~~~~^~~~~~~~~~
sprinkler.cpp: In function 'void solve()':
sprinkler.cpp:207:27: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  207 |         for (int j = 0; j < d[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 2 ms 1628 KB Output is correct
5 Incorrect 3 ms 1372 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 583 ms 197968 KB Output is correct
3 Correct 695 ms 194992 KB Output is correct
4 Correct 668 ms 274664 KB Output is correct
5 Correct 583 ms 196164 KB Output is correct
6 Correct 603 ms 196256 KB Output is correct
7 Correct 597 ms 195840 KB Output is correct
8 Correct 554 ms 195272 KB Output is correct
9 Correct 639 ms 276052 KB Output is correct
10 Correct 749 ms 273136 KB Output is correct
11 Correct 551 ms 197696 KB Output is correct
12 Correct 696 ms 194884 KB Output is correct
13 Correct 453 ms 194852 KB Output is correct
14 Correct 533 ms 196036 KB Output is correct
15 Correct 577 ms 194956 KB Output is correct
16 Correct 568 ms 195244 KB Output is correct
17 Correct 615 ms 194772 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 583 ms 197968 KB Output is correct
3 Correct 695 ms 194992 KB Output is correct
4 Correct 668 ms 274664 KB Output is correct
5 Correct 583 ms 196164 KB Output is correct
6 Correct 603 ms 196256 KB Output is correct
7 Correct 597 ms 195840 KB Output is correct
8 Correct 554 ms 195272 KB Output is correct
9 Correct 639 ms 276052 KB Output is correct
10 Correct 749 ms 273136 KB Output is correct
11 Correct 551 ms 197696 KB Output is correct
12 Correct 696 ms 194884 KB Output is correct
13 Correct 453 ms 194852 KB Output is correct
14 Correct 533 ms 196036 KB Output is correct
15 Correct 577 ms 194956 KB Output is correct
16 Correct 568 ms 195244 KB Output is correct
17 Correct 615 ms 194772 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Incorrect 530 ms 197712 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1271 ms 273880 KB Output is correct
3 Execution timed out 4054 ms 272912 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1265 ms 276384 KB Output is correct
3 Execution timed out 4049 ms 273116 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 2 ms 1628 KB Output is correct
5 Incorrect 3 ms 1372 KB Output isn't correct
6 Halted 0 ms 0 KB -