oj.uz

Submission #678997

# Submission time Handle Problem Language Result Execution time Memory
678997 2023-01-07T07:20:48 Z jhwest2 Sprinkler (JOI22_sprinkler) C++17
0 / 100
 167 ms 51704 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 202020;
const int M = 44;

int n, mod, q;
vector<int> g[N];

int sub[N], dep[N], gp[N], a[N];
bool dead[N];

void pre_dfs(int p, int v) {
    sub[v] = 1;
    for (int x : g[v]) {
        if (p == x || dead[x])
            continue;

        pre_dfs(v, x);
        sub[v] += sub[x];
    }
}
int find_centroid(int p, int v, int z) {
    for (int x : g[v]) {
        if (p == x || dead[x])
            continue;
        
        if (2 * sub[x] > z)
            return find_centroid(v, x, z);
    }
    return v;
}
void dfs(int p, int v, int z) {
    gp[v] = z;
    dep[v] = dep[p] + 1;
    for (int x : g[v]) {
        if (p == x || dead[x])
            continue;

        dfs(v, x, z);
    }
}
struct query {
    int t, x, d, w, i;
};
vector<query> qr[N];
int ans[N];

struct fenwick {
    int tree[N];

    void init(int sz) {
        fill(tree, tree + sz + 1, 1);
    }
    void update(int a, int x) {
        for (; a < N; a += a & -a) 
            tree[a] = 1ll * tree[a] * x % mod;
    }
    int query(int a) {
        int res = 1;
        for (; a; a -= a & -a)
            res = 1ll * res * tree[a] % mod;
        return res;
    }
} t1[M], t2[M];

void solve(int v) {
    pre_dfs(v, v);
    int centroid = find_centroid(v, v, sub[v]);

    dep[centroid] = 0;
    for (int i = 0; i < g[centroid].size(); i++)
        if (!dead[g[centroid][i]]) 
            dfs(centroid, g[centroid][i], i);

    if (v != centroid) {
        qr[centroid] = qr[v];
        vector<query>().swap(qr[v]);
    }

    int sz = g[centroid].size();

    for (int i = 0; i < M; i++) {
        t1[i].init(sz);
        t2[i].init(sz);
    }

    vector<int> s(M, 1);
    for (auto [t, x, d, w, i] : qr[centroid]) {
        if (x != centroid)
            qr[g[centroid][gp[x]]].push_back({t, x, d, w, i});

        if (t == 1) {
            if (dep[x] > d)
                continue;
            if (x == centroid)
                s[d] = 1ll * s[d] * w % mod;
            else {
                t1[d - dep[x]].update(gp[x] + 1, w);
                t2[d - dep[x]].update(sz - gp[x], w);
            }
            // cout << v << ' ' << centroid << ' ' << x << ' ' << d - dep[x] << ' ' << gp[x] << ' ' << w << '\n';
        }
        else {
            for (int j = dep[x]; j < M; j++) {
                if (x == centroid)
                    ans[i] = 1ll * ans[i] * t1[j].query(sz);
                else {
                    if (gp[x]) 
                        ans[i] = 1ll * ans[i] * t1[j].query(gp[x]);
                    if (gp[x] != sz - 1) 
                        ans[i] = 1ll * ans[i] * t2[j].query(sz - gp[x] - 1);
                }
                ans[i] = 1ll * ans[i] * s[j] % mod;
            }
        }
    }
    dead[centroid] = 1;

    for (int i = 0; i < g[centroid].size(); i++)
        if (!dead[g[centroid][i]])
            solve(g[centroid][i]);
}
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> mod;
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    cin >> q;
    int sz = 0;
    for (int i = 1; i <= q; i++) {
        int t; cin >> t;
        if (t == 1) {
            int x, d, w; cin >> x >> d >> w;
            qr[1].push_back({t, x, d, w, 0});
        }
        else {
            int x; cin >> x;
            qr[1].push_back({t, x, 0, 0, ++sz});
            ans[sz] = a[x];
        }
    }

    solve(1);

    for (int i = 1; i <= sz; i++)
        cout << ans[i] << '\n';

}

Compilation message

sprinkler.cpp: In function 'void solve(int)':
sprinkler.cpp:72:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for (int i = 0; i < g[centroid].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~~~~
sprinkler.cpp:120:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |     for (int i = 0; i < g[centroid].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10452 KB Output is correct
2 Correct 5 ms 10324 KB Output is correct
3 Correct 5 ms 10336 KB Output is correct
4 Incorrect 9 ms 13140 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10336 KB Output is correct
2 Runtime error 167 ms 51704 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 6 ms 10336 KB Output is correct
2 Runtime error 167 ms 51704 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 5 ms 10452 KB Output is correct
2 Runtime error 146 ms 51336 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 6 ms 10340 KB Output is correct
2 Runtime error 148 ms 51332 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 5 ms 10452 KB Output is correct
2 Correct 5 ms 10324 KB Output is correct
3 Correct 5 ms 10336 KB Output is correct
4 Incorrect 9 ms 13140 KB Output isn't correct
5 Halted 0 ms 0 KB -