oj.uz

Submission #894010

# Submission time Handle Problem Language Result Execution time Memory
894010 2023-12-27T19:10:29 Z azosi Min-max tree (BOI18_minmaxtree) C++17
100 / 100
 287 ms 32036 KB 
#include <bits/stdc++.h>

#define x first
#define y second
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 pv;
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 op, int k) {
    while (top[a] != top[b]) {
        if (dep[top[a]] < dep[top[b]]) swap(a, b);
        int st = top[a];
        if (op == 1) minSeg.update(in[st], in[a], k);
        else 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 maxi[MAX_N], mini[MAX_N], cnt[MAX_N], ans[MAX_N], vis[MAX_N];

struct Query {
    int s, e, x, mx;
};
vector<Query> qry;
map<int, int> mp;
vector<int> bench[MAX_N];

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 a, b, c;
        cin >> op >> a >> b >> c;
        if (op == 'm') update(a, b, 2, c);
        else update(a, b, 1, c);
        qry.push_back({a, b, c, op == 'M'});
        zz.push_back(c);
    }

    for (int i = 0; i < q; i++) {
        mp[zz[i]] = i;
    }
    memset(maxi, -1, sizeof maxi);
    memset(mini, -1, sizeof mini);
    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[mp[maxi[i]]].push_back(i);
        }
        if (mini[i] != INF) {
            bench[mp[mini[i]]].push_back(i);
        }
    }

    memset(chk, 0, sizeof chk);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    for (int i = 0; i < q; i++) {
        cnt[mp[zz[i]]] = bench[mp[zz[i]]].size();
        pq.push({cnt[mp[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 (chk[node]) continue;
            ans[node] = zz[id];
            chk[node] = true;
            if (maxi[node] != -INF && !vis[mp[maxi[node]]]) {
                cnt[mp[maxi[node]]]--;
                pq.push({cnt[mp[maxi[node]]], mp[maxi[node]]});
            }
            if (mini[node] != INF && !vis[mp[mini[node]]]) {
                cnt[mp[mini[node]]]--;
                pq.push({cnt[mp[mini[node]]], mp[mini[node]]});
            }
            break;
        }

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

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12636 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Correct 4 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 204 ms 29568 KB Output is correct
2 Correct 244 ms 25360 KB Output is correct
3 Correct 212 ms 26804 KB Output is correct
4 Correct 226 ms 30768 KB Output is correct
5 Correct 213 ms 26260 KB Output is correct
6 Correct 228 ms 26528 KB Output is correct
7 Correct 210 ms 25928 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 19908 KB Output is correct
2 Correct 126 ms 20240 KB Output is correct
3 Correct 107 ms 23984 KB Output is correct
4 Correct 103 ms 25680 KB Output is correct
5 Correct 116 ms 21668 KB Output is correct
6 Correct 132 ms 22232 KB Output is correct
7 Correct 131 ms 20984 KB Output is correct
8 Correct 119 ms 21036 KB Output is correct

Subtask #4
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12636 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Correct 4 ms 12636 KB Output is correct
4 Correct 3 ms 12632 KB Output is correct
5 Correct 204 ms 29568 KB Output is correct
6 Correct 244 ms 25360 KB Output is correct
7 Correct 212 ms 26804 KB Output is correct
8 Correct 226 ms 30768 KB Output is correct
9 Correct 213 ms 26260 KB Output is correct
10 Correct 228 ms 26528 KB Output is correct
11 Correct 210 ms 25928 KB Output is correct
12 Correct 115 ms 19908 KB Output is correct
13 Correct 126 ms 20240 KB Output is correct
14 Correct 107 ms 23984 KB Output is correct
15 Correct 103 ms 25680 KB Output is correct
16 Correct 116 ms 21668 KB Output is correct
17 Correct 132 ms 22232 KB Output is correct
18 Correct 131 ms 20984 KB Output is correct
19 Correct 119 ms 21036 KB Output is correct
20 Correct 283 ms 25304 KB Output is correct
21 Correct 239 ms 23540 KB Output is correct
22 Correct 267 ms 23544 KB Output is correct
23 Correct 215 ms 23436 KB Output is correct
24 Correct 257 ms 30468 KB Output is correct
25 Correct 238 ms 32036 KB Output is correct
26 Correct 246 ms 30648 KB Output is correct
27 Correct 287 ms 29772 KB Output is correct
28 Correct 274 ms 26536 KB Output is correct
29 Correct 235 ms 26760 KB Output is correct
30 Correct 271 ms 24680 KB Output is correct
31 Correct 231 ms 24952 KB Output is correct
32 Correct 269 ms 26396 KB Output is correct
33 Correct 247 ms 24864 KB Output is correct
34 Correct 268 ms 24760 KB Output is correct
35 Correct 237 ms 24724 KB Output is correct