oj.uz

Submission #1003584

# Submission time Handle Problem Language Result Execution time Memory
1003584 2024-06-20T13:21:46 Z onbert Sprinkler (JOI22_sprinkler) C++17
9 / 100
 1052 ms 183492 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 4e5 + 5, maxN = 2e6 + 5, m = 43;
int n, M;
vector<int> adj[maxn];
int newid[maxn], d[maxn], fa[maxn], a[maxn];
bool vis[maxn];

pair<int,int> range[maxn][m];
void dfs(int u) {
    range[u][0] = {newid[u], newid[u]};
    if (adj[u].size() == 0) return;
    for (int v:adj[u]) dfs(v);
    int sz = adj[u].size();
    int l = 0, r = sz - 1;
    for (int i=1;i<m;i++) {
        while (l < sz && range[adj[u][l]][i-1].first==-1) l++;
        while (r >= 0 && range[adj[u][r]][i-1].first==-1) r--;
        if (l>r) break;
        range[u][i] = {range[adj[u][l]][i-1].first, range[adj[u][r]][i-1].second};
    }
}

int seg[maxN];
void build(int id, int l, int r) {
    seg[id] = 1;
    if (l==r) {
        seg[id] = a[l];
        return;
    }
    int mid = (l+r)/2;
    build(id*2, l, mid); build(id*2+1, mid+1, r);
}
void update(int id, int l, int r, int findl, int findr, int val) {
    if (r<findl || findr<l) return;
    if (findl<=l && r<=findr) {
        seg[id] = seg[id] * val % M;
        return;
    }
    int mid = (l+r)/2;
    update(id*2, l, mid, findl, findr, val);
    update(id*2+1, mid+1, r, findl, findr, val);
}
int qry(int id, int l, int r, int target) {
    if (r<target || target<l) return 1;
    if (l==r) return seg[id];
    int mid = (l+r)/2;
    return (seg[id] * qry(id*2, l, mid, target) % M) * qry(id*2+1, mid+1, r, target) % M;
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> M;
    for (int i=1;i<=n-1;i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    int A[n+1];
    for (int i=1;i<=n;i++) cin >> A[i];
    queue<int> Q;
    Q.push(1);
    vis[1] = true, d[1] = 0, fa[1] = -1;
    int cnter = 0;
    while (Q.size() > 0) {
        int u = Q.front();
        cnter++;
        newid[u] = cnter;
        for (int v:adj[u]) if (!vis[v]) {
            vis[v] = true, fa[v] = u, d[v] = d[u] + 1;
            adj[v].erase(find(adj[v].begin(), adj[v].end(), u));
            Q.push(v);
        }
        Q.pop();
    }
    for (int i=1;i<=n;i++) for (int j=0;j<m;j++) range[i][j] = {-1, -1};
    dfs(1);
    for (int i=1;i<=n;i++) a[newid[i]] = A[i];
    build(1, 1, n);
    int q;
    cin >> q;
    while (q--) {
        int t;
        cin >> t;
        if (t==1) {
            int x, D, w;
            cin >> x >> D >> w;
            for (int i=0;i<=D;i++) if (range[x][i].first!=-1) update(1, 1, n, range[x][i].first, range[x][i].second, w);
            for (int u = fa[x]; u!=-1 && d[u]>=d[x]-D; u = fa[u]) {
                // cout << u << endl;
                update(1, 1, n, newid[u], newid[u], w);
            }
        } else if (t==2) {
            int x;
            cin >> x;
            cout << qry(1, 1, n, newid[x]) << endl;
        }
        // for (int i=1;i<=n;i++) cout << qry(1, 1, n, newid[i]) << " "; cout << endl;
    }
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9816 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 3 ms 9820 KB Output is correct
4 Incorrect 6 ms 10496 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10072 KB Output is correct
2 Correct 695 ms 175700 KB Output is correct
3 Correct 475 ms 176208 KB Output is correct
4 Correct 585 ms 180892 KB Output is correct
5 Correct 623 ms 176176 KB Output is correct
6 Correct 524 ms 175724 KB Output is correct
7 Correct 471 ms 176464 KB Output is correct
8 Correct 476 ms 178260 KB Output is correct
9 Correct 704 ms 183492 KB Output is correct
10 Correct 554 ms 183380 KB Output is correct
11 Correct 623 ms 175700 KB Output is correct
12 Correct 477 ms 176272 KB Output is correct
13 Correct 368 ms 177856 KB Output is correct
14 Correct 321 ms 177656 KB Output is correct
15 Correct 341 ms 176308 KB Output is correct
16 Correct 333 ms 177004 KB Output is correct
17 Correct 342 ms 177232 KB Output is correct
18 Correct 4 ms 9820 KB Output is correct
19 Correct 5 ms 9816 KB Output is correct
20 Correct 5 ms 9816 KB Output is correct
21 Correct 4 ms 9820 KB Output is correct
22 Correct 5 ms 9816 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10072 KB Output is correct
2 Correct 695 ms 175700 KB Output is correct
3 Correct 475 ms 176208 KB Output is correct
4 Correct 585 ms 180892 KB Output is correct
5 Correct 623 ms 176176 KB Output is correct
6 Correct 524 ms 175724 KB Output is correct
7 Correct 471 ms 176464 KB Output is correct
8 Correct 476 ms 178260 KB Output is correct
9 Correct 704 ms 183492 KB Output is correct
10 Correct 554 ms 183380 KB Output is correct
11 Correct 623 ms 175700 KB Output is correct
12 Correct 477 ms 176272 KB Output is correct
13 Correct 368 ms 177856 KB Output is correct
14 Correct 321 ms 177656 KB Output is correct
15 Correct 341 ms 176308 KB Output is correct
16 Correct 333 ms 177004 KB Output is correct
17 Correct 342 ms 177232 KB Output is correct
18 Correct 4 ms 9820 KB Output is correct
19 Correct 5 ms 9816 KB Output is correct
20 Correct 5 ms 9816 KB Output is correct
21 Correct 4 ms 9820 KB Output is correct
22 Correct 5 ms 9816 KB Output is correct
23 Correct 4 ms 9820 KB Output is correct
24 Incorrect 715 ms 175604 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9820 KB Output is correct
2 Incorrect 1037 ms 180772 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9816 KB Output is correct
2 Incorrect 1052 ms 180212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9816 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 3 ms 9820 KB Output is correct
4 Incorrect 6 ms 10496 KB Output isn't correct
5 Halted 0 ms 0 KB -