제출 #59737

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
59737		model_code	Min-max tree (BOI18_minmaxtree)	C++17	100 / 100	642 ms	35996 KiB

minmaxtree

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

const int INF = 0x3f3f3f3f;

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<multiset<pair<int, int>>> vmax, vmin;
vector<int> treeSize;
vector<int> minValue, maxValue;
vector<int> parent;

void dfs(int node, int prev) {
    parent[node] = prev;
    treeSize[node] = 1;
    int v = -1;
    for (int to: tree[node]) {
        if (to != prev) {
            dfs(to, node);
            treeSize[node] += treeSize[to];
            if (v == -1 || treeSize[to] > treeSize[v]) {
                v = to;
            }
        }
    }
    set<pair<int, int>> toRemoveMin, toRemoveMax;
    if (v == -1) {
        v = node;
        for (const auto& v: vmin[node]) {
            if (vmin[node].count(v) > 1) {
                toRemoveMin.insert(v);
            }
        }
        for (const auto& v: vmax[node]) {
            if (vmax[node].count(v) > 1) {
                toRemoveMax.insert(v);
            }
        }
    } else {
        tree[node].push_back(node);
        for (int to: tree[node]) {
            if (to == prev || to == v) {
                continue;
            }
            for (const auto &p: vmax[to]) {
                if (vmax[v].count(p)) {
                    toRemoveMax.insert(p);
                } else {
                    vmax[v].insert(p);
                }
            }
            for (const auto &p: vmin[to]) {
                if (vmin[v].count(p)) {
                    toRemoveMin.insert(p);
                } else {
                    vmin[v].insert(p);
                }
            }
        }
        tree[node].pop_back();
        vmin[node] = move(vmin[v]);
        vmax[node] = move(vmax[v]);
    }
    for (const auto& p: toRemoveMin) {
        vmin[node].erase(p);
    }
    for (const auto& p: toRemoveMax) {
        vmax[node].erase(p);
    }
    minValue[node] = vmin[node].empty() ? -INF: last(vmin[node])->first;
    maxValue[node] = vmax[node].empty() ? INF: begin(vmax[node])->first;
}

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;
    cin >> n;
    tree.resize(n);
    parent.resize(n);
    for (int i = 1; i < n; ++i) {
        int x, y;
        cin >> x >> y;
        x--; y--;
        tree[x].push_back(y);
        tree[y].push_back(x);
    }
    vmax.resize(n);
    vmin.resize(n);
    int m;
    cin >> m;

    while (m-- > 0) {
        char type;
        int n1, n2, w;
        cin >> type >> n1 >> n2 >> w;
        n1--; n2--;
        (type == 'M' ? vmax: vmin)[n1].insert(make_pair(w, m));
        (type == 'M' ? vmax: vmin)[n2].insert(make_pair(w, m));
    }
    treeSize.resize(n);
    minValue.resize(n);
    maxValue.resize(n);
    dfs(0, -1);
    
    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();
    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