oj.uz

Submission #894013

# Submission time Handle Problem Language Result Execution time Memory
894013 2023-12-27T19:18:47 Z azosi Min-max tree (BOI18_minmaxtree) C++17
100 / 100
 278 ms 30032 KB 
#include <bits/stdc++.h>

using namespace std;
const int MAX_N = 70070;
const int INF = 1e9 + 100;
int n, q;

struct SegmentTree {
    typedef int (*F)(int, int);

    F merge;
    int identity;
    int tree[MAX_N * 4]{}, lazy[MAX_N * 4]{};

    SegmentTree(F func, int identity) : merge(func), identity(identity) {
        for (int i = 0; i < MAX_N * 4; ++i) tree[i] = lazy[i] = identity;
    }

    void push(int node, int l, int r) {
        if (lazy[node] != identity) {
            tree[node] = merge(tree[node], lazy[node]);
            if (l != r) {
                lazy[node * 2] = merge(lazy[node * 2], lazy[node]);
                lazy[node * 2 + 1] = merge(lazy[node * 2 + 1], lazy[node]);
            }
        }
        lazy[node] = identity;
    }

    void update(int s, int e, int val, int node = 1, int l = 1, int r = MAX_N) {
        push(node, l, r);
        if (e < l || r < s) return;
        if (s <= l && r <= e) {
            lazy[node] = val;
            push(node, l, r);
            return;
        }
        int mid = (l + r) / 2;
        update(s, e, val, node * 2, l, mid);
        update(s, e, val, node * 2 + 1, mid + 1, r);
        tree[node] = merge(tree[node * 2], tree[node * 2 + 1]);
    }

    int query(int s, int e, int node = 1, int l = 1, int r = MAX_N) {
        push(node, l, r);
        if (e < l || r < s) return identity;
        if (s <= l && r <= e) return tree[node];
        int mid = (l + r) / 2;
        return merge(query(s, e, node * 2, l, mid), query(s, e, node * 2 + 1, mid + 1, r));
    }

};

int _mn(int a, int b) {
    return min(a, b);
}

int _mx(int a, int b) {
    return max(a, b);
}

SegmentTree minSeg(_mn, INF), maxSeg(_mx, -INF);
int in[MAX_N], dep[MAX_N], par[MAX_N], top[MAX_N], sz[MAX_N], chk[MAX_N];
int maxi[MAX_N], mini[MAX_N], cnt[MAX_N], ans[MAX_N], vis[MAX_N];
int pv;
map<int, int> toIdx;
vector<int> bench[MAX_N];
vector<int> g[MAX_N], inp[MAX_N];

void dfs(int v = 1) {
    chk[v] = 1;
    for (auto i: inp[v]) {
        if (chk[i]) continue;
        chk[i] = 1;
        g[v].push_back(i);
        dfs(i);
    }
}

void dfs1(int v = 1) {
    sz[v] = 1;
    for (auto &i: g[v]) {
        dep[i] = dep[v] + 1;
        par[i] = v;
        dfs1(i);
        sz[v] += sz[i];
        if (sz[i] > sz[g[v][0]]) swap(i, g[v][0]);
    }
}

void dfs2(int v = 1) {
    in[v] = ++pv;
    for (auto i: g[v]) {
        top[i] = i == g[v][0] ? top[v] : i;
        dfs2(i);
    }
}

void update(int a, int b, int k, bool op) {
    while (top[a] != top[b]) {
        if (dep[top[a]] < dep[top[b]]) swap(a, b);
        int st = top[a];
        op ? minSeg.update(in[st], in[a], k) : maxSeg.update(in[st], in[a], k);
        a = par[st];
    }
    if (dep[a] > dep[b]) swap(a, b);
    if (op == 1) minSeg.update(in[a] + 1, in[b], k);
    else maxSeg.update(in[a] + 1, in[b], k);
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n;
    top[1] = 1;
    for (int i = 2; i <= n; i++) {
        int s, e;
        cin >> s >> e;
        inp[s].push_back(e);
        inp[e].push_back(s);
    }
    dfs();
    dfs1();
    dfs2();

    cin >> q;
    vector<int> zz;
    for (int i = 0; i < q; i++) {
        char op;
        int x, y, z;
        cin >> op >> x >> y >> z;
        if (op == 'm') update(x, y, z, false);
        else update(x, y, z, true);
        zz.push_back(z);
    }

    for (int i = 0; i < q; i++) {
        toIdx[zz[i]] = i;
    }
    for (int i = 2; i <= n; i++) {
        maxi[i] = maxSeg.query(in[i], in[i]);
        mini[i] = minSeg.query(in[i], in[i]);
        if (maxi[i] != -INF) {
            bench[toIdx[maxi[i]]].push_back(i);
        }
        if (mini[i] != INF) {
            bench[toIdx[mini[i]]].push_back(i);
        }
    }

    for (auto &i: ans) i = INF;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    for (int i = 0; i < q; i++) {
        cnt[toIdx[zz[i]]] = bench[toIdx[zz[i]]].size();
        pq.push({cnt[toIdx[zz[i]]], i});
    }
    while (!pq.empty()) {
        auto [am, id] = pq.top();
        pq.pop();
        if (am != cnt[id]) continue;
        vis[id] = true;

        for (auto node: bench[id]) {
            if (ans[node] != INF) continue;
            ans[node] = zz[id];
            if (maxi[node] != -INF && !vis[toIdx[maxi[node]]]) {
                cnt[toIdx[maxi[node]]]--;
                pq.emplace(cnt[toIdx[maxi[node]]], toIdx[maxi[node]]);
            }
            if (mini[node] != INF && !vis[toIdx[mini[node]]]) {
                cnt[toIdx[mini[node]]]--;
                pq.emplace(cnt[toIdx[mini[node]]], toIdx[mini[node]]);
            }
            break;
        }

    }
    for (int i = 2; i <= n; i++) {
        cout << par[i] << " " << i << " ";
        if (ans[i] != INF) {
            cout << ans[i] << "\n";
        } else {
            cout << maxi[i] << '\n';
        }
    }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12636 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Correct 3 ms 12636 KB Output is correct
4 Correct 3 ms 12632 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 27508 KB Output is correct
2 Correct 220 ms 23284 KB Output is correct
3 Correct 193 ms 25548 KB Output is correct
4 Correct 197 ms 28992 KB Output is correct
5 Correct 200 ms 24912 KB Output is correct
6 Correct 242 ms 24644 KB Output is correct
7 Correct 190 ms 23888 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 19572 KB Output is correct
2 Correct 124 ms 19644 KB Output is correct
3 Correct 96 ms 23756 KB Output is correct
4 Correct 101 ms 25036 KB Output is correct
5 Correct 118 ms 21144 KB Output is correct
6 Correct 127 ms 21444 KB Output is correct
7 Correct 131 ms 20560 KB Output is correct
8 Correct 123 ms 20272 KB Output is correct

Subtask #4
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12636 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Correct 3 ms 12636 KB Output is correct
4 Correct 3 ms 12632 KB Output is correct
5 Correct 202 ms 27508 KB Output is correct
6 Correct 220 ms 23284 KB Output is correct
7 Correct 193 ms 25548 KB Output is correct
8 Correct 197 ms 28992 KB Output is correct
9 Correct 200 ms 24912 KB Output is correct
10 Correct 242 ms 24644 KB Output is correct
11 Correct 190 ms 23888 KB Output is correct
12 Correct 109 ms 19572 KB Output is correct
13 Correct 124 ms 19644 KB Output is correct
14 Correct 96 ms 23756 KB Output is correct
15 Correct 101 ms 25036 KB Output is correct
16 Correct 118 ms 21144 KB Output is correct
17 Correct 127 ms 21444 KB Output is correct
18 Correct 131 ms 20560 KB Output is correct
19 Correct 123 ms 20272 KB Output is correct
20 Correct 278 ms 23372 KB Output is correct
21 Correct 221 ms 22348 KB Output is correct
22 Correct 228 ms 22696 KB Output is correct
23 Correct 220 ms 22548 KB Output is correct
24 Correct 248 ms 28648 KB Output is correct
25 Correct 267 ms 30032 KB Output is correct
26 Correct 234 ms 29520 KB Output is correct
27 Correct 266 ms 27796 KB Output is correct
28 Correct 266 ms 24664 KB Output is correct
29 Correct 257 ms 24624 KB Output is correct
30 Correct 218 ms 23504 KB Output is correct
31 Correct 238 ms 23628 KB Output is correct
32 Correct 236 ms 24136 KB Output is correct
33 Correct 261 ms 23632 KB Output is correct
34 Correct 237 ms 23628 KB Output is correct
35 Correct 225 ms 23384 KB Output is correct