oj.uz

Submission #334029

# Submission time Handle Problem Language Result Execution time Memory
334029 2020-12-08T06:51:01 Z thecodingwizard Min-max tree (BOI18_minmaxtree) C++11
100 / 100
 625 ms 51544 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];
}

struct FlowEdge {
    int to, rev;
    ll cap, flow;
};

struct Dinic {
    const ll flow_inf = 1e18;
    vector<vector<FlowEdge>> adj;
    int n;
    void init(int _n) {
        n = _n;
        adj.resize(n);
    }
    void add_edge(int u, int v, ll cap) {
        adj[u].pb(FlowEdge{v, sz(adj[v]), cap, 0LL});
        adj[v].pb(FlowEdge{u, sz(adj[u])-1, 0LL, 0LL});
    }
    vector<int> level, ptr;
    bool bfs(int s, int t) { // level = shortest distance from source
        level = ptr = vector<int>(n);
        level[s] = 1; queue<int> q({s});
        while (sz(q)) {
            int u = q.front(); q.pop();
            for (auto e : adj[u]) {
                if (e.flow < e.cap && !level[e.to]) {
                    q.push(e.to); level[e.to] = level[u]+1;
                }
            }
        }
        return level[t];
    }
    ll dfs(int v, int t, ll flow) {
        if (v == t) return flow;
        for (int &i = ptr[v]; i < sz(adj[v]); i++) {
            FlowEdge &e = adj[v][i];
            ll diff = e.cap - e.flow;
            if (level[e.to] != level[v]+1 || !diff) continue;
            if (ll df = dfs(e.to, t, min(flow, diff))) {
                e.flow += df; adj[e.to][e.rev].flow -= df;
                return df;
            }
        }
        return 0;
    }
    ll maxFlow(int s, int t) {
        ll tot = 0;
        while (bfs(s, t)) {
            while (ll df = dfs(s, t, flow_inf)) tot += df;
        }
        return tot;
    }
};

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> values;
    FOR(i, 1, n) {
        values.insert(m[i]);
        values.insert(M[i]);
    }
    int ctr = 0;
    map<int, int> compress;
    map<int, int> compressRev;
    for (int x : values) {
        if (x >= 0 && x != inf) {
            compressRev[ctr] = x;
            compress[x] = ctr++;
        }
    }

    Dinic mf; mf.init(n+ctr+1);
    FOR(i, 1, n) {
        mf.add_edge(0, i, 1);
        // cout << i << "-->" << pa[i][0] << ": " << m[i] << " "<< M[i] << endl;
        if (compress.count(m[i])) mf.add_edge(i, n+compress[m[i]], 1);
        if (compress.count(M[i])) mf.add_edge(i, n+compress[M[i]], 1);
    }
    F0R(i, ctr) {
        mf.add_edge(n+i, n+ctr, 1);
    }
    mf.maxFlow(0, n+ctr);

    FOR(i, 1, n) {
        int numEdges = 0;
        for (auto e : mf.adj[i]) {
            if (e.flow <= 0) continue;
            cout << i+1 << " " << pa[i][0]+1 << " " << compressRev[e.to-n] << "\n";
            numEdges++;
        }
        assert(numEdges <= 1);
        if (numEdges == 0) {
            cout << i+1 << " " << pa[i][0]+1 << " " << m[i] << "\n";
        }
    }

    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2028 KB Output is correct
2 Correct 2 ms 2028 KB Output is correct
3 Correct 2 ms 2028 KB Output is correct
4 Correct 2 ms 2028 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 386 ms 44360 KB Output is correct
2 Correct 344 ms 42080 KB Output is correct
3 Correct 340 ms 39816 KB Output is correct
4 Correct 388 ms 45312 KB Output is correct
5 Correct 351 ms 40540 KB Output is correct
6 Correct 370 ms 42816 KB Output is correct
7 Correct 336 ms 42076 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 28808 KB Output is correct
2 Correct 212 ms 30420 KB Output is correct
3 Correct 189 ms 29304 KB Output is correct
4 Correct 174 ms 30264 KB Output is correct
5 Correct 236 ms 32020 KB Output is correct
6 Correct 257 ms 32988 KB Output is correct
7 Correct 250 ms 32216 KB Output is correct
8 Correct 237 ms 31760 KB Output is correct

Subtask #4
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2028 KB Output is correct
2 Correct 2 ms 2028 KB Output is correct
3 Correct 2 ms 2028 KB Output is correct
4 Correct 2 ms 2028 KB Output is correct
5 Correct 386 ms 44360 KB Output is correct
6 Correct 344 ms 42080 KB Output is correct
7 Correct 340 ms 39816 KB Output is correct
8 Correct 388 ms 45312 KB Output is correct
9 Correct 351 ms 40540 KB Output is correct
10 Correct 370 ms 42816 KB Output is correct
11 Correct 336 ms 42076 KB Output is correct
12 Correct 213 ms 28808 KB Output is correct
13 Correct 212 ms 30420 KB Output is correct
14 Correct 189 ms 29304 KB Output is correct
15 Correct 174 ms 30264 KB Output is correct
16 Correct 236 ms 32020 KB Output is correct
17 Correct 257 ms 32988 KB Output is correct
18 Correct 250 ms 32216 KB Output is correct
19 Correct 237 ms 31760 KB Output is correct
20 Correct 551 ms 45652 KB Output is correct
21 Correct 379 ms 40604 KB Output is correct
22 Correct 384 ms 40476 KB Output is correct
23 Correct 393 ms 41044 KB Output is correct
24 Correct 579 ms 50956 KB Output is correct
25 Correct 564 ms 51544 KB Output is correct
26 Correct 512 ms 49564 KB Output is correct
27 Correct 550 ms 50512 KB Output is correct
28 Correct 574 ms 47124 KB Output is correct
29 Correct 543 ms 47576 KB Output is correct
30 Correct 490 ms 43364 KB Output is correct
31 Correct 470 ms 44112 KB Output is correct
32 Correct 625 ms 47344 KB Output is correct
33 Correct 501 ms 44568 KB Output is correct
34 Correct 496 ms 44620 KB Output is correct
35 Correct 502 ms 43736 KB Output is correct