Submission #1258926

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258926		herominhsteve	Min-max tree (BOI18_minmaxtree)	C++20	100 / 100	157 ms	37844 KiB

minmaxtree

#include <bits/stdc++.h>
using namespace std;

#define allof(x) (x).begin(), (x).end()
#define el '\n'

const int MAXN = 70005;
const int LOG = 17;
const int INF = 1e9+7;

// -------- input --------
struct Query {
    char type; // 'M' or 'm'
    int u, v, w;
};

// -------- tree / HLD --------
int n, K;
vector<int> g[MAXN];
int parent_[MAXN], depth_[MAXN], heavy[MAXN], head[MAXN], pos[MAXN], sz[MAXN];
int curPos;

int up_bin[MAXN][LOG+1]; // for optional LCA via binary lifting if needed

int edge_id_of_node[MAXN]; // edge index for edge(parent[u] -- u), 1..n-1 (0 for root)
int eu[MAXN], ev[MAXN];    // edges 1..n-1
int which_edge[MAXN][2];   // not used; placeholder if you want u->edge

// -------- queries --------
vector<Query> qs;          // 1..K (we'll index from 1)
unordered_map<int,int> qid_by_w; // map z -> query id (1..K)

// -------- events for sweep --------
vector<pair<int,int>> add_ev[MAXN], rem_ev[MAXN]; // (w, bit) bit=0 for min, 1 for max

// -------- edge bounds --------
int lo_edge[MAXN]; // max of active mins  on that edge
int up_edge[MAXN]; // min of active maxs  on that edge

// -------- matching graph: Left = queries (1..K), Right = edges (1..n-1) --------
vector<int> adjQ[MAXN]; // adj from query to candidate edges

// Hopcroft-Karp arrays
int distHK[MAXN], matchQ[MAXN], matchE[MAXN]; // matchQ[q] = edge, matchE[e] = query
queue<int> qHK;

int dfs_sz(int u, int p) {
    parent_[u] = p;
    depth_[u] = (p ? depth_[p] + 1 : 0);
    up_bin[u][0] = p;
    for (int k=1; k<=LOG; k++) up_bin[u][k] = up_bin[ up_bin[u][k-1] ][k-1];

    sz[u] = 1;
    int mx = 0;
    heavy[u] = 0;
    for (int v : g[u]) if (v != p) {
        int s = dfs_sz(v,u);
        sz[u] += s;
        if (s > mx) mx = s, heavy[u] = v;
    }
    return sz[u];
}

void decomp(int u, int h, int p, int &edge_counter) {
    head[u] = h;
    pos[u] = ++curPos;
    if (p) {
        edge_id_of_node[u] = ++edge_counter;
    } else {
        edge_id_of_node[u] = 0; // root has no parent edge
    }
    if (heavy[u]) decomp(heavy[u], h, u, edge_counter);
    for (int v : g[u]) if (v != p && v != heavy[u]) {
        decomp(v, v, u, edge_counter);
    }
}

int lca_hld(int a, int b) {
    while (head[a] != head[b]) {
        if (depth_[head[a]] > depth_[head[b]]) a = parent_[head[a]];
        else b = parent_[head[b]];
    }
    return depth_[a] < depth_[b] ? a : b;
}

inline void range_add_events(int L, int R, int w, int bit) {
    if (L > R) return;
    add_ev[L].push_back({w, bit});
    rem_ev[R].push_back({w, bit});
}

void add_path_events(int u, int v, int w, int bit) {
    while (head[u] != head[v]) {
        if (depth_[head[u]] >= depth_[head[v]]) {
            int top = head[u];
            // edges along nodes [pos[top] .. pos[u]], all covered except the parent of 'top'.
            range_add_events(pos[top], pos[u], w, bit);
            u = parent_[top];
        } else {
            int top = head[v];
            range_add_events(pos[top], pos[v], w, bit);
            v = parent_[top];
        }
    }
    if (depth_[u] < depth_[v]) swap(u, v); // ensure u is deeper
    if (u != v) {
        range_add_events(pos[v]+1, pos[u], w, bit);
    }
}

// ---------- Hopcroft–Karp ----------
bool bfs_HK(int K_left) {
    queue<int> q;
    for (int i=1;i<=K_left;i++){
        if (matchQ[i] == 0) distHK[i] = 0, q.push(i);
        else distHK[i] = -1;
    }
    bool reachable_free_edge = false;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int e : adjQ[u]) {
            int v = matchE[e];
            if (v == 0) {
                reachable_free_edge = true;
            } else if (distHK[v] == -1) {
                distHK[v] = distHK[u] + 1;
                q.push(v);
            }
        }
    }
    return reachable_free_edge;
}

bool dfs_HK(int u) {
    for (int e : adjQ[u]) {
        int v = matchE[e];
        if (v == 0 || (distHK[v] == distHK[u] + 1 && dfs_HK(v))) {
            matchQ[u] = e;
            matchE[e] = u;
            return true;
        }
    }
    distHK[u] = -1;
    return false;
}

int hopcroft_karp(int K_left, int E_right) {
    for (int i=1;i<=K_left;i++) matchQ[i] = 0;
    for (int e=1;e<=E_right;e++) matchE[e] = 0;
    int matching = 0;
    while (bfs_HK(K_left)) {
        for (int i=1;i<=K_left;i++) {
            if (matchQ[i] == 0) {
                if (dfs_HK(i)) matching++;
            }
        }
    }
    return matching;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i=1;i<n;i++) {
        int u,v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
        eu[i] = u; ev[i] = v;
    }
    cin >> K;
    qs.resize(K+1);
    for (int i=1;i<=K;i++) {
        char t; int u,v,w;
        cin >> t >> u >> v >> w;
        qs[i] = {t,u,v,w};
        qid_by_w[w] = i;
    }

    dfs_sz(1,0);
    int edge_counter = 0;
    decomp(1,1,0,edge_counter);
    for (int i=1;i<=K;i++) {
        int u = qs[i].u, v = qs[i].v, w = qs[i].w;
        int bit = (qs[i].type == 'M') ? 1 : 0; // 0=min, 1=max
        add_path_events(u, v, w, bit);
    }

    for (int e=1;e<=n-1;e++) lo_edge[e] = -INF, up_edge[e] = INF;

    multiset<int> activeMin, activeMax;
    for (int p=1;p<=n;p++) {
        for (auto pr : add_ev[p]) {
            int w = pr.first, bit = pr.second;
            if (bit == 0) activeMin.insert(w);
            else activeMax.insert(w);
        }

        int u = 0;
        static bool built_inv = false;
        static int invPos[MAXN];
        if (!built_inv) {
            for (int v=1; v<=n; v++) invPos[pos[v]] = v;
            built_inv = true;
        }
        u = invPos[p];

        int e = edge_id_of_node[u];
        if (e) {
            if (!activeMin.empty()) lo_edge[e] = max(lo_edge[e], *activeMin.rbegin());
            if (!activeMax.empty()) up_edge[e] = min(up_edge[e], *activeMax.begin());
        }

        for (auto pr : rem_ev[p]) {
            int w = pr.first, bit = pr.second;
            if (bit == 0) {
                auto it = activeMin.find(w);
                if (it != activeMin.end()) activeMin.erase(it);
            } else {
                auto it = activeMax.find(w);
                if (it != activeMax.end()) activeMax.erase(it);
            }
        }
    }

    for (int e=1;e<=n-1;e++) {
        if (lo_edge[e] != -INF) {
            auto it = qid_by_w.find(lo_edge[e]);
            if (it != qid_by_w.end()) {
                adjQ[it->second].push_back(e);
            }
        }
        if (up_edge[e] != INF && up_edge[e] != lo_edge[e]) {
            auto it = qid_by_w.find(up_edge[e]);
            if (it != qid_by_w.end()) {
                adjQ[it->second].push_back(e);
            }
        }
    }

    int Msize = hopcroft_karp(K, n-1);

    vector<int> ans(n); 
    for (int e=1;e<=n-1;e++) {
        int val = 0;
        if (lo_edge[e] != -INF) val = lo_edge[e];
        if (up_edge[e] != INF) val = min(val, up_edge[e]); 
        ans[e] = val;
    }

    for (int q=1;q<=K;q++) {
        int e = matchQ[q];
        if (e) ans[e] = qs[q].w;
    }

    unordered_map<long long,int> mapEdge;
    mapEdge.reserve(n*2);
    auto keyOf = [&](int a, int b)->long long {
        if (a>b) swap(a,b);
        return ( (long long)a << 32 ) ^ (long long)b;
    };
    for (int u=2; u<=n; u++) {
        int p = parent_[u];
        int e = edge_id_of_node[u];
        mapEdge[keyOf(p,u)] = e;
    }

    // Print in the original input order
    for (int i=1;i<=n-1;i++) {
        int u = eu[i], v = ev[i];
        int e = mapEdge[keyOf(u,v)];
        cout << u << ' ' << v << ' ' << ans[e] << el;
    }
    return 0;
}

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