oj.uz

Submission #59737

# Submission time Handle Problem Language Result Execution time Memory
59737 2018-07-23T02:01:53 Z model_code Min-max tree (BOI18_minmaxtree) C++17
100 / 100
 642 ms 35996 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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