oj.uz

답안 #334021

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
334021 2020-12-08T06:18:11 Z thecodingwizard Min-max tree (BOI18_minmaxtree) C++11
29 / 100
 1000 ms 26204 KB 
#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.0 / 7.0

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

Subtask #2
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 312 ms 25692 KB Output is correct
2 Correct 282 ms 23520 KB Output is correct
3 Correct 721 ms 24132 KB Output is correct
4 Correct 313 ms 26204 KB Output is correct
5 Correct 563 ms 23904 KB Output is correct
6 Correct 293 ms 24156 KB Output is correct
7 Correct 281 ms 23516 KB Output is correct

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1051 ms 18944 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 3692 KB Output is correct
2 Correct 3 ms 3692 KB Output is correct
3 Correct 3 ms 3684 KB Output is correct
4 Correct 3 ms 3692 KB Output is correct
5 Correct 312 ms 25692 KB Output is correct
6 Correct 282 ms 23520 KB Output is correct
7 Correct 721 ms 24132 KB Output is correct
8 Correct 313 ms 26204 KB Output is correct
9 Correct 563 ms 23904 KB Output is correct
10 Correct 293 ms 24156 KB Output is correct
11 Correct 281 ms 23516 KB Output is correct
12 Execution timed out 1051 ms 18944 KB Time limit exceeded
13 Halted 0 ms 0 KB -