제출 #334021

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
334021		thecodingwizard	Min-max tree (BOI18_minmaxtree)	C++11	29 / 100	1051 ms	26204 KiB

minmaxtree

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define ii pair<int, int>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define F0R(i, n) for (int i = 0; i < n; i++)
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define inf 1000000010

#define maxn 70000
vector<int> adj[maxn];
int pa[maxn][18];
int depth[maxn];
int m[maxn], M[maxn];

void dfs(int u, int p, int d) {
    pa[u][0] = p;
    depth[u] = d;
    for (int v : adj[u]) if (v != p) dfs(v, u, d+1);
}

int lca(int a, int b) {
    if (depth[a] < depth[b]) swap(a, b);
    for (int i = 17; ~i; i--) {
        if (depth[pa[a][i]] >= depth[b]) a = pa[a][i];
    }
    if (a == b) return a;
    for (int i = 17; ~i; i--) {
        if (pa[a][i] != pa[b][i]) {
            a = pa[a][i];
            b = pa[b][i];
        }
    }
    return pa[a][0];
}

bool vis[maxn];
map<int, int> match;
vector<int> flowAdj[maxn];

int aug(int x) {
    if (vis[x]) return 0;
    vis[x] = true;
    for (int y : flowAdj[x]) {
        if (y == inf || y == -1) continue;
        if (match[y] == -1 || aug(match[y])) {
            match[y] = x;
            return 1;
        }
    }
    return 0;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    int n; cin >> n;
    F0R(i, n-1) {
        int x, y; cin >> x >> y; --x; --y;
        adj[x].pb(y); adj[y].pb(x);
    }
    dfs(0, 0, 0);
    FOR(i, 1, 18) {
        F0R(j, n) {
            pa[j][i] = pa[pa[j][i-1]][i-1];
        }
    }
    int k; cin >> k;
    vector<pair<int, ii>> minimum, maximum;
    F0R(i, k) {
        char c; cin >> c;
        int a, b, w; cin >> a >> b >> w; --a; --b;
        int l = lca(a, b);
        if (c == 'M') {
            maximum.pb(mp(w, mp(a, l)));
            maximum.pb(mp(w, mp(b, l)));
        } else {
            minimum.pb(mp(w, mp(a, l)));
            minimum.pb(mp(w, mp(b, l)));
        }
    }
    sort(all(maximum));
    sort(all(minimum));
    reverse(all(minimum));

    vector<int> nxt(n);
    F0R(i, n) nxt[i] = pa[i][0];
    F0R(i, n) M[i] = inf;
    for (auto event : maximum) {
        int v = event.f, a = event.s.f, b = event.s.s;
        vector<int> toUpd;
        while (depth[a] > depth[b]) {
            M[a] = min(M[a], v);
            toUpd.pb(a);
            a = nxt[a];
        }
        for (auto x : toUpd) {
            nxt[x] = a;
        }
    }
    F0R(i, n) nxt[i] = pa[i][0];
    F0R(i, n) m[i] = -1;
    for (auto event : minimum) {
        int v = event.f, a = event.s.f, b = event.s.s;
        vector<int> toUpd;
        while (depth[a] > depth[b]) {
            m[a] = max(m[a], v);
            toUpd.pb(a);
            a = nxt[a];
        }
        for (auto x : toUpd) {
            nxt[x] = a;
        }
    }

    set<int> freeV;
    FOR(i, 1, n) {
        // cout << i << "-->" << pa[i][0] << ": " << m[i] << " "<< M[i] << endl;
        flowAdj[i].pb(m[i]);
        flowAdj[i].pb(M[i]);
        match[m[i]] = match[M[i]] = -1;
        freeV.insert(i);
    }

    int flow = 0;
    FOR(i, 1, n) {
        vector<int> candidates;
        for (auto r : flowAdj[i]) {
            if (r == inf || r == -1) continue;
            if (match[r] == -1) candidates.pb(r);
        }
        if (sz(candidates)>0) {
            flow++;
            freeV.erase(i);
            int idx = rand()%sz(candidates);
            match[candidates[idx]] = i;
        }
    }

    for (auto x : freeV) {
        fill(vis, vis+n, false);
        flow += aug(x);
    }

    fill(vis, vis+n, false);
    for (auto x : match) {
        if (x.f == inf || x.f == -1) continue;
        assert(x.s != -1);
        cout << x.s+1 << " " << pa[x.s][0]+1 << " " << x.f << "\n";
        vis[x.s] = true;
    }

    FOR(i, 1, n) {
        if (!vis[i]) {
            cout << i+1 << " " << pa[i][0]+1 << " " << m[i] << "\n";
        }
    }

    return 0;
}

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