Submission #59740

#	Time	Username	Problem	Language	Result	Execution time	Memory
59740		model_code	Min-max tree (BOI18_minmaxtree)	C++17	100 / 100	604 ms	32500 KiB

minmaxtree

#include <algorithm>
#include <cassert>
#include <iostream>
#include <functional>
#include <set>
#include <vector>
#define SZ(x) ((int) (x).size())
using namespace std;

const int INF = 0x3f3f3f3f;

const int LOG_N = 18;

class GeneralBipartiteMatcher {
public:
    GeneralBipartiteMatcher(int n, int m):
            adj(n), m(m) {}
    void addEdge(int from, int to) {
        adj[from].push_back(to);
    }
    vector<int> matching() const {
        int n = SZ(adj);
        vector<int> l(n, -1), r(m, -1);
        vector<bool> used(n, false);
        for (bool ok = true; ok; ) {
            ok = false;
            fill(used.begin(), used.end(), false);
            for (int node = 0; node < n; ++node) {
                if (l[node] == -1) {
                    ok |= pairUp(l, r, used, node);
                }
            }
        }
        return l;
    }
private:
    vector<vector<int>> adj;
    int m;

    bool pairUp(vector<int>& l, vector<int>& r, vector<bool>& used, int node) const {
        if (used[node]) {
            return false;
        }
        used[node] = true;
        for (int to: adj[node]) {
            if (r[to] == -1) {
                l[node] = to;
                r[to] = node;
                return true;
            }
        }
        for (int to: adj[node]) {
            if (pairUp(l, r, used, r[to])) {
                l[node] = to;
                r[to] = node;
                return true;
            }
        }
        return false;
    }
};

typedef GeneralBipartiteMatcher Matcher;

template<class E>
typename multiset<E>::iterator last(const multiset<E>& m) {
    auto it = m.end();
    --it;
    return it;
}

vector<vector<int>> tree;
vector<int> parent, level;

void dfs(int node, int prev) {
    parent[node] = prev;
    for (int to: tree[node]) {
        if (to != prev) {
            level[to] = level[node] + 1;
            dfs(to, node);
        }
    }
}

vector<int> norm(vector<int> a) {
    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());
    return a;
}

int main() {
    int n;
    assert(cin >> n);
    assert(1 <= n && n <= 70000);
    tree.resize(n);
    parent.resize(n);
    level.resize(n, -1);
    for (int i = 1; i < n; ++i) {
        int x, y;
        assert(cin >> x >> y);
        assert(1 <= x && x <= n);
        assert(1 <= y && y <= n);
        x--; y--;
        tree[x].push_back(y);
        tree[y].push_back(x);
    }
    level[0] = 0;
    dfs(0, -1);
    assert(find(level.begin(), level.end(), -1) == level.end());
    parent[0] = 0;

    vector<vector<int>> anc(LOG_N, vector<int>(n));
    vector<vector<int>> vmax(LOG_N, vector<int>(n, INF));
    vector<vector<int>> vmin(LOG_N, vector<int>(n, -INF));
    anc[0] = parent;
    for (int k = 1; k < LOG_N; ++k) {
        for (int node = 0; node < n; ++node) {
            anc[k][node] = anc[k - 1][anc[k - 1][node]];
        }
    }
    function<int(int, int)> min = [](int a, int b) -> int {
        return a < b ? a: b;
    };
    function<int(int, int)> max = [](int a, int b) -> int {
        return a > b ? a: b;
    };
    auto goUp = [&](int x, int lvl, int val, const function<int(int, int)>& func, vector<vector<int>>& vec) {
        for (int k = LOG_N - 1; k >= 0; --k) {
            if (lvl & (1 << k)) {
                vec[k][x] = func(vec[k][x], val);
                x = anc[k][x];
            }
        }
        return x;
    };
    auto putLca = [&](int x, int y, int val, const function<int(int, int)>& func, vector<vector<int>>& vec) {
        if (level[x] > level[y]) {
            x = goUp(x, level[x] - level[y], val, func, vec);
        } else if (level[y] > level[x]) {
            y = goUp(y, level[y] - level[x], val, func, vec);
        }
        if (x == y) {
            return;
        }
        for (int k = LOG_N - 1; k >= 0; --k) {
            if (anc[k][x] != anc[k][y]) {
                vec[k][x] = func(vec[k][x], val);
                vec[k][y] = func(vec[k][y], val);
                x = anc[k][x];
                y = anc[k][y];
            }
        }
        vec[0][x] = func(vec[0][x], val);
        vec[0][y] = func(vec[0][y], val);
    };

    int m;
    cin >> m;
    assert(1 <= m && m <= 70000);
    multiset<int> s;
    for (int i = 0; i < m; ++i) {
        char type;
        int n1, n2, w;
        assert(cin >> type >> n1 >> n2 >> w);
        assert(type == 'M' || type == 'm');
        assert(1 <= n1 && n1 <= n);
        assert(1 <= n2 && n2 <= n);
        assert(1 <= w && w <= 1000000000);
        assert(!s.count(w));
        s.insert(w);
        n1--; n2--;
        if (type == 'M') {
            putLca(n1, n2, w, min, vmax);
        } else {
            putLca(n1, n2, w, max, vmin);
        }
    }
    for (int k = LOG_N - 1; k > 0; --k) {
        for (int node = 0; node < n; ++node) {
            vmin[k - 1][node] = max(vmin[k - 1][node], vmin[k][node]);
            vmin[k - 1][anc[k - 1][node]] = max(vmin[k - 1][anc[k - 1][node]], vmin[k][node]);
            vmax[k - 1][node] = min(vmax[k - 1][node], vmax[k][node]);
            vmax[k - 1][anc[k - 1][node]] = min(vmax[k - 1][anc[k - 1][node]], vmax[k][node]);
        }
    }
    vector<int> minValue = move(vmin[0]);
    vector<int> maxValue = move(vmax[0]);

    vector<int> mins = norm(minValue);
    if (mins[0] == -INF) {
        mins.erase(mins.begin());
    }
    vector<int> maxs = norm(maxValue);
    if (maxs.back() == INF) {
        maxs.erase(maxs.end() - 1);
    }
    Matcher matcher(n, SZ(mins) + SZ(maxs));
    for (int i = 0; i < n; ++i) {
        if (minValue[i] != -INF) {
            int pos = (int) (lower_bound(mins.begin(), mins.end(), minValue[i]) - mins.begin());
            matcher.addEdge(i, pos);
        }
        if (maxValue[i] != INF) {
            int pos = (int) (lower_bound(maxs.begin(), maxs.end(), maxValue[i]) - maxs.begin());
            matcher.addEdge(i, SZ(mins) + pos);
        }
    }
    vector<int> matching = matcher.matching();
    int cnt = 0;
    for (int x: matching) {
        cnt += x != -1;
    }
    assert(cnt == m);
    vector<int> values(n);
    for (int i = 0; i < n; ++i) {
        if (0 <= matching[i] && matching[i] < SZ(mins)) {
            values[i] = mins[matching[i]];
        } else if (SZ(mins) <= matching[i] && matching[i]) {
            values[i] = maxs[matching[i] - SZ(mins)];
        } else if (minValue[i] != -INF) {
            values[i] = minValue[i];
        } else if (maxValue[i] != INF) {
            values[i] = maxValue[i];
        } else {
            values[i] = 7;
        }
    }
    for (int i = 1; i < n; ++i) {
        cout << i + 1 << ' ' << parent[i] + 1 << ' ' << values[i] << '\n';
    }
}

• Subtask 1: 7 / 7
• Subtask 2: 22 / 22
• Subtask 3: 29 / 29
• Subtask 4: 42 / 42