답안 #59737 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
59737	2018-07-23T02:01:53 Z	model_code	Min-max tree (BOI18_minmaxtree)	C++17	100 / 100	642 ms	35996 KB

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.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	248 KB	Output is correct
2	Correct	3 ms	484 KB	Output is correct
3	Correct	2 ms	484 KB	Output is correct
4	Correct	3 ms	484 KB	Output is correct

Subtask #2
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	555 ms	30848 KB	Output is correct
2	Correct	460 ms	30848 KB	Output is correct
3	Correct	642 ms	30848 KB	Output is correct
4	Correct	554 ms	33136 KB	Output is correct
5	Correct	480 ms	33136 KB	Output is correct
6	Correct	440 ms	33136 KB	Output is correct
7	Correct	366 ms	33136 KB	Output is correct

Subtask #3
29.0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	242 ms	33136 KB	Output is correct
2	Correct	233 ms	33136 KB	Output is correct
3	Correct	250 ms	33136 KB	Output is correct
4	Correct	318 ms	33136 KB	Output is correct
5	Correct	307 ms	33136 KB	Output is correct
6	Correct	394 ms	33136 KB	Output is correct
7	Correct	384 ms	33136 KB	Output is correct
8	Correct	333 ms	33136 KB	Output is correct

Subtask #4
42.0 / 42.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	248 KB	Output is correct
2	Correct	3 ms	484 KB	Output is correct
3	Correct	2 ms	484 KB	Output is correct
4	Correct	3 ms	484 KB	Output is correct
5	Correct	555 ms	30848 KB	Output is correct
6	Correct	460 ms	30848 KB	Output is correct
7	Correct	642 ms	30848 KB	Output is correct
8	Correct	554 ms	33136 KB	Output is correct
9	Correct	480 ms	33136 KB	Output is correct
10	Correct	440 ms	33136 KB	Output is correct
11	Correct	366 ms	33136 KB	Output is correct
12	Correct	242 ms	33136 KB	Output is correct
13	Correct	233 ms	33136 KB	Output is correct
14	Correct	250 ms	33136 KB	Output is correct
15	Correct	318 ms	33136 KB	Output is correct
16	Correct	307 ms	33136 KB	Output is correct
17	Correct	394 ms	33136 KB	Output is correct
18	Correct	384 ms	33136 KB	Output is correct
19	Correct	333 ms	33136 KB	Output is correct
20	Correct	571 ms	33136 KB	Output is correct
21	Correct	638 ms	33136 KB	Output is correct
22	Correct	627 ms	33136 KB	Output is correct
23	Correct	582 ms	33136 KB	Output is correct
24	Correct	594 ms	33136 KB	Output is correct
25	Correct	588 ms	35996 KB	Output is correct
26	Correct	593 ms	35996 KB	Output is correct
27	Correct	512 ms	35996 KB	Output is correct
28	Correct	533 ms	35996 KB	Output is correct
29	Correct	482 ms	35996 KB	Output is correct
30	Correct	468 ms	35996 KB	Output is correct
31	Correct	607 ms	35996 KB	Output is correct
32	Correct	487 ms	35996 KB	Output is correct
33	Correct	548 ms	35996 KB	Output is correct
34	Correct	498 ms	35996 KB	Output is correct
35	Correct	450 ms	35996 KB	Output is correct

답안 #59737

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 22.0 / 22.0

Subtask #3 29.0 / 29.0

Subtask #4 42.0 / 42.0

Subtask #1
7.0 / 7.0

Subtask #2
22.0 / 22.0

Subtask #3
29.0 / 29.0

Subtask #4
42.0 / 42.0