Submission #955193

#	Time	Username	Problem	Language	Result	Execution time	Memory
955193		vjudge1	Min-max tree (BOI18_minmaxtree)	C++17	100 / 100	732 ms	113592 KiB

minmaxtree

#include<bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define int long long int
using namespace std;

const int64_t INF = 1e17;
const int mod = 1e9+7;

vector<int> tree[100001];

struct LCA {
    
    
    vector<int> height, euler, first, segtree;
    vector<bool> visited;
    int n;

    LCA(int n) : n(n) {
        height.resize(n + 1);
        first.resize(n + 1, -1);
        euler.reserve(n * 2);
        visited.assign(n + 1, false);
    }

    void dfs(int node, int h = 0) {
        visited[node] = true;
        height[node] = h;
        first[node] = euler.size();
        euler.push_back(node);
        for (auto to : tree[node]) {
            if (!visited[to]) {
                dfs(to, h + 1);
                euler.push_back(node);
            }
        }
    }

    int build(int node, int b, int e) {
        if (b == e) {
            return segtree[node] = euler[b];
        } else {
            int mid = (b + e) / 2;
            int left = build(node * 2, b, mid);
            int right = build(node * 2 + 1, mid + 1, e);
            return segtree[node] = (height[left] < height[right] ? left : right);
        }
    }

    void init() {
        dfs(1);
        int m = euler.size();
        segtree.assign(m * 4, -1);
        build(1, 0, m - 1);
    }

    int query(int node, int b, int e, int L, int R) {
        if (b > R || e < L)
            return -1;
        if (b >= L && e <= R)
            return segtree[node];
        int mid = (b + e) / 2;
        int left = query(node * 2, b, mid, L, R);
        int right = query(node * 2 + 1, mid + 1, e, L, R);
        if (left == -1) return right;
        if (right == -1) return left;
        return height[left] < height[right] ? left : right;
    }

    int lca(int u, int v) {
        int left = first[u], right = first[v];
        if (left > right)
            swap(left, right);
        return query(1, 0, euler.size() - 1, left, right);
    }

};

struct Dinic {

    struct Edge {
        int to, cap, rev;
    };
    vector<vector<Edge>> G;
    vector<int> level, iter;
    Dinic(int n) : G(n), level(n), iter(n) {}
    void add_edge(int from, int to, int cap) {
        G[from].push_back({to, cap, (int)G[to].size()});
        G[to].push_back({from, 0, (int)G[from].size() - 1});
    }
    void bfs(int s) {
        fill(level.begin(), level.end(), -1);
        queue<int> que;
        level[s] = 0;
        que.push(s);
        while (!que.empty()) {
            int v = que.front();
            que.pop();
            for (auto &e : G[v]) {
                if (e.cap > 0 && level[e.to] < 0) {
                    level[e.to] = level[v] + 1;
                    que.push(e.to);
                }
            }
        }
    }
    int dfs(int v, int t, int f) {
        if (v == t) return f;
        for (int &i = iter[v]; i < (int)G[v].size(); i++) {
            Edge &e = G[v][i];
            if (e.cap > 0 && level[v] < level[e.to]) {
                int d = dfs(e.to, t, min(f, e.cap));
                if (d > 0) {
                    e.cap -= d;
                    G[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
    int max_flow(int s, int t) {
        int flow = 0;
        while (true) {
            bfs(s);
            if (level[t] < 0) return flow;
            fill(iter.begin(), iter.end(), 0);
            int f;
            while ((f = dfs(s, t, INT_MAX)) > 0) {
                flow += f;
            }
        }
    }

    set<pair<int, int>> get_full_edges() {
        set<pair<int, int>> full_edges;
        for (int i = 0; i < G.size(); i++) {
            for (auto &e : G[i]) {
                if (e.cap == 0) {
                    full_edges.insert({i, e.to});
                }
            }
        }
        return full_edges;
    }

}; 

const int MAXN = 1e5 + 5;

vector<pair<int, int>> edges;

map<int, int> enumerate_assignments;
map<pair<int, int>, int> enumerate_edges;

map<pair<int, int>, int> max_assignments;
map<pair<int, int>, int> min_assignments;

vector<int> max_path_removal[MAXN];
vector<int> min_path_removal[MAXN];
set<int> path_max[MAXN];
set<int> path_min[MAXN];

struct Query {
    char type;
    int u, v, z;
};
vector<Query> queries;




void assign_max(int u, int p) {
    
    for (int v : tree[u]) {
        if (v == p) continue;
        assign_max(v, u);

        if (path_max[v].size() > path_max[u].size()) {
            swap(path_max[u], path_max[v]);
        }

        for (auto z : path_max[v]) {
            path_max[u].insert(z);
        }
    }

    for (int z : max_path_removal[u]) {
        path_max[u].erase(z);
    }

    if (p != 0 && !path_max[u].empty()) {
        max_assignments[{min(u, p), max(u, p)}] = *path_max[u].begin();
    }

}

void assign_min(int u, int p) {
        
    for (int v : tree[u]) {
        if (v == p) continue;
        assign_min(v, u);

        if (path_min[v].size() > path_min[u].size()) {
            swap(path_min[u], path_min[v]);
        }

        for (auto z : path_min[v]) {
            path_min[u].insert(z);
        }
    }

    for (int z : min_path_removal[u]) {
        path_min[u].erase(z);
    }

    if (p != 0 && !path_min[u].empty()) {
        min_assignments[{min(u, p), max(u, p)}] = *path_min[u].rbegin();
    }
}

Dinic run_flow() {

    int source = 1, sink = 2;
    int last = 3;

    for (auto query : queries) {
        enumerate_assignments[query.z] = last++;
    }

    for (auto& itr : edges) {
        enumerate_edges[itr] = last++;
    }

    Dinic dinic(last + 1);

    for (auto& itr : enumerate_assignments) {
        dinic.add_edge(source, itr.second, 1);
    }

    for (auto& itr : max_assignments) {
        dinic.add_edge(enumerate_assignments[itr.second], enumerate_edges[itr.first], 1);
    }

    for (auto& itr : min_assignments) {
        dinic.add_edge(enumerate_assignments[itr.second], enumerate_edges[itr.first], 1);
    }

    for (auto& itr : edges) {
        dinic.add_edge(enumerate_edges[itr], sink, 1);
    }
    
    int flow = dinic.max_flow(source, sink);

    // cerr << flow << '\n';

    return dinic;

}


int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    for(int i = 0; i < n - 1; i++){
        int u, v;
        cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);

        if (u > v) swap(u, v);
        edges.push_back({u, v});
    }

    LCA lca(n + 1);

    lca.init();

    int q;
    cin >> q;

    while (q--) {
        char type;
        int u, v, z;
        cin >> type >> u >> v >> z;

        queries.push_back({type, u, v, z});

        if (type == 'M') {
            max_path_removal[lca.lca(u, v)].push_back(z);
            path_max[u].insert(z);
            path_max[v].insert(z);
        }
        else {
            min_path_removal[lca.lca(u, v)].push_back(z);
            path_min[u].insert(z);
            path_min[v].insert(z);
        }

    }

    assign_max(1, 0);
    assign_min(1, 0);
    
    Dinic dinic = run_flow();

    set<pair<int, int>> full_edges = dinic.get_full_edges();
    map<pair<int, int>, int> answer;

     for (auto& itr : max_assignments) {
        if (full_edges.count({enumerate_assignments[itr.second], enumerate_edges[itr.first]})) {
            answer[itr.first] = itr.second;
        }
    }

    for (auto& itr : min_assignments) {
        if (full_edges.count({enumerate_assignments[itr.second], enumerate_edges[itr.first]})) {
            answer[itr.first] = itr.second;
        }
    }

    for (auto itr : edges) {
        cout << itr.first << ' ' << itr.second << ' ';
        if (answer.count(itr)) {
            cout << answer[itr] << '\n';
        }
        else if (max_assignments.count(itr)) {
            cout << max_assignments[itr] << '\n';
        }
        else if (min_assignments.count(itr)) {
            cout << min_assignments[itr] << '\n';
        }
        else {
            cout << 0 << '\n';
        }
    }

}

Compilation message (stderr)

minmaxtree.cpp: In member function 'std::set<std::pair<long long int, long long int> > Dinic::get_full_edges()':
minmaxtree.cpp:136:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<Dinic::Edge> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |         for (int i = 0; i < G.size(); i++) {
      |                         ~~^~~~~~~~~~
minmaxtree.cpp: In function 'Dinic run_flow()':
minmaxtree.cpp:252:9: warning: unused variable 'flow' [-Wunused-variable]
  252 |     int flow = dinic.max_flow(source, sink);
      |         ^~~~

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