제출 #59736

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

minmaxtree

#include <bits/stdc++.h>

using namespace std;

const int NMAX = 100000 + 5;

int N;
vector <int> tree[NMAX];
int fathers[NMAX], h[NMAX];
void dfs(int node) {
    for (auto it: tree[node])
        if (it != fathers[node]) {
            h[it] = 1 + h[node], fathers[it] = node;
            dfs(it);
        }
}

int father[NMAX], lowest[NMAX];
inline void init() {
    for (int i = 1; i <= N; ++ i)
        father[i] = lowest[i] = i;
}
inline int find(int node) {
    if (father[father[node]] != father[node])
        father[node] = find(father[node]);
    return father[node];
}
inline void unite(int a, int b) {
    a = find(a), b = find(b);
    if (a == b)
        return ;
    if (rand() & 1)
        father[a] = b;
    else
        father[b] = a, lowest[a] = lowest[b];
}

int queryValues[NMAX];
struct Query {
    int a, b, index;
    Query(int _a = 0, int _b = 0, int _index = 0):
        a(_a), b(_b), index(_index) {}
    friend bool operator<(const Query &arg0, const Query &arg1) {
        return queryValues[arg0.index] < queryValues[arg1.index];
    }
};
vector <Query> minQueries, maxQueries;

int lowerBound[NMAX], upperBound[NMAX];
void mark(int bound[], int a, int b, int index) {
    a = lowest[find(a)], b = lowest[find(b)];
    while (a != b) {
        if (h[a] > h[b])
            swap(a, b);
        bound[b] = index;
        unite(b, fathers[b]);
        b = lowest[find(b)];
    }
}

vector <int> matchGraph[NMAX];
int l[NMAX], r[NMAX];
bool vis[NMAX];

bool pairUp(int node) {
    if (vis[node])
        return false;
    vis[node] = true;
    for (auto it: matchGraph[node])
        if (!r[it] || pairUp(r[it])) {
            l[node] = it, r[it] = node;
            return true;
        }
    return false;
}

void hopcroft() {
    bool ok = true;
    while (ok) {
        ok = false;
        for (int i = 2; i <= N; ++ i)
            vis[i] = false;
        for (int i = 2; i <= N; ++ i)
            if (!l[i] && pairUp(i))
                ok = true;
    }
}

int main() {
    ios_base :: sync_with_stdio(false);
    //freopen("minmaxarb.in", "r", stdin);

    cin >> N;
    for (int i = 1; i < N; ++ i) {
        int a, b;
        cin >> a >> b;
        tree[a].push_back(b), tree[b].push_back(a);
    }
    dfs(1);

    int M;
    cin >> M;

    for (int i = 1; i <= M; ++ i) {
        char type;
        cin >> type;

        int a, b, c;
        cin >> a >> b >> c;
        queryValues[i] = c;

        assert(c > 0);

        if (type == 'm')
            minQueries.emplace_back(a, b, i);
        else
            maxQueries.emplace_back(a, b, i);
    }

    sort(maxQueries.begin(), maxQueries.end());
    sort(minQueries.begin(), minQueries.end());
    reverse(minQueries.begin(), minQueries.end());

    init();
    for (auto it: maxQueries)
        mark(upperBound, it.a, it.b, it.index);
    init();
    for (auto it: minQueries)
        mark(lowerBound, it.a, it.b, it.index);

    for (int i = 2; i <= N; ++ i) {
        if (lowerBound[i])
            matchGraph[i].push_back(lowerBound[i]);
        if (upperBound[i])
            matchGraph[i].push_back(upperBound[i]);
    }

    hopcroft();
    for (int i = 2; i <= N; ++ i) {
        int val = queryValues[l[i]];
        if (!l[i]) {
            if (lowerBound[i])
                val = queryValues[lowerBound[i]];
            else
                val = 1;
        }
        cout << i << ' ' << fathers[i] << ' ' << val << '\n';
    }
    return 0;
}

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