Submission #1263451

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263451		gary	Min-max tree (BOI18_minmaxtree)	C++20	36 / 100	1095 ms	23308 KiB

minmaxtree

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

const int INF = 1000000000;

struct Edge {
    int to, id;
};
int n;

// ---------- HLD ----------
vector<vector<Edge>> g;
vector<int> parent, depth, heavy, sz, head, pos;
vector<int> edgeIdAtPos; // maps position -> original edge id (for edge mapped to child node)
int curPos;

int dfs_sz(int v, int p) {
    parent[v] = p;
    sz[v] = 1;
    heavy[v] = -1;
    int maxsz = 0;
    for (auto& e : g[v]) {
        int to = e.to;
        if (to == p) continue;
        depth[to] = depth[v] + 1;
        int s = dfs_sz(to, v);
        if (s > maxsz) {
            maxsz = s;
            heavy[v] = to;
        }
        sz[v] += s;
    }
    return sz[v];
}
void dfs_hld(int v, int h, int pedge_id = -1) {
    head[v] = h;
    pos[v] = ++curPos;
    // map the edge that connects v to parent (if exists) to position pos[v]
    if (pedge_id != -1) edgeIdAtPos[pos[v]] = pedge_id;
    if (heavy[v] != -1) {
        // heavy edge uses same head
        int hid = -1;
        // find edge id of heavy edge
        for (auto& e : g[v])
            if (e.to == heavy[v]) {
                hid = e.id;
                break;
            }
        dfs_hld(heavy[v], h, hid);
    }
    for (auto& e : g[v]) {
        int to = e.to;
        if (to == parent[v] || to == heavy[v]) continue;
        dfs_hld(to, to, e.id);
    }
}

// ---------- Segment tree supporting range chmax ----------
struct SegChMax {
    int n;
    vector<int> st, lazy;
    SegChMax(int _n = 0) { init(_n); }
    void init(int _n) {
        n = 1;
        while (n < _n)
            n <<= 1;
        st.assign(2 * n, -INF);
        lazy.assign(2 * n, -INF);
    }
    void apply(int v, int x) {
        st[v] = max(st[v], x);
        lazy[v] = max(lazy[v], x);
    }
    void push(int v) {
        if (lazy[v] != -INF) {
            apply(v << 1, lazy[v]);
            apply(v << 1 | 1, lazy[v]);
            lazy[v] = -INF;
        }
    }
    void update(int v, int l, int r, int ql, int qr, int x) {
        if (ql > r || qr < l) return;
        if (ql <= l && r <= qr) {
            apply(v, x);
            return;
        }
        push(v);
        int m = (l + r) >> 1;
        update(v << 1, l, m, ql, qr, x);
        update(v << 1 | 1, m + 1, r, ql, qr, x);
        st[v] = min(st[v << 1], st[v << 1 | 1]); // value not really used except propagation: keep something
    }
    void update_range(int l, int r, int x) {
        if (l > r) return;
        update(1, 1, n, l, r, x);
    }
    int query_point(int v, int l, int r, int posq) {
        if (l == r) return st[v];
        push(v);
        int m = (l + r) >> 1;
        if (posq <= m)
            return query_point(v << 1, l, m, posq);
        else
            return query_point(v << 1 | 1, m + 1, r, posq);
    }
    int query_point(int p) { return query_point(1, 1, n, p); }
};

// ---------- Segment tree supporting range chmin ----------
struct SegChMin {
    int n;
    vector<int> st, lazy;
    SegChMin(int _n = 0) { init(_n); }
    void init(int _n) {
        n = 1;
        while (n < _n)
            n <<= 1;
        st.assign(2 * n, INF);
        lazy.assign(2 * n, INF);
    }
    void apply(int v, int x) {
        st[v] = min(st[v], x);
        lazy[v] = min(lazy[v], x);
    }
    void push(int v) {
        if (lazy[v] != INF) {
            apply(v << 1, lazy[v]);
            apply(v << 1 | 1, lazy[v]);
            lazy[v] = INF;
        }
    }
    void update(int v, int l, int r, int ql, int qr, int x) {
        if (ql > r || qr < l) return;
        if (ql <= l && r <= qr) {
            apply(v, x);
            return;
        }
        push(v);
        int m = (l + r) >> 1;
        update(v << 1, l, m, ql, qr, x);
        update(v << 1 | 1, m + 1, r, ql, qr, x);
        st[v] = max(st[v << 1], st[v << 1 | 1]); // not important, kept for structure
    }
    void update_range(int l, int r, int x) {
        if (l > r) return;
        update(1, 1, n, l, r, x);
    }
    int query_point(int v, int l, int r, int posq) {
        if (l == r) return st[v];
        push(v);
        int m = (l + r) >> 1;
        if (posq <= m)
            return query_point(v << 1, l, m, posq);
        else
            return query_point(v << 1 | 1, m + 1, r, posq);
    }
    int query_point(int p) { return query_point(1, 1, n, p); }
};

// HLD wrapper to update edges on path u-v (edges are mapped to nodes except LCA)
void update_path_edges(int u, int v, int x, bool isLowerUpdate, SegChMax& segL, SegChMin& segU) {
    while (head[u] != head[v]) {
        if (depth[head[u]] < depth[head[v]]) swap(u, v);
        int h = head[u];
        // update positions pos[h] .. pos[u] (these are nodes) BUT edges correspond to pos[child], so we update whole segment
        if (isLowerUpdate)
            segL.update_range(pos[h], pos[u], x);
        else
            segU.update_range(pos[h], pos[u], x);
        u = parent[h];
    }
    // now same head
    if (depth[u] < depth[v]) swap(u, v);
    // nodes from v..u, but edges exclude v (the LCA), so update pos[v]+1 .. pos[u]
    if (pos[v] + 1 <= pos[u]) {
        if (isLowerUpdate)
            segL.update_range(pos[v] + 1, pos[u], x);
        else
            segU.update_range(pos[v] + 1, pos[u], x);
    }
}

// collect edge positions on path u-v
void collect_edge_positions_on_path(int u, int v, vector<int>& outPos) {
    while (head[u] != head[v]) {
        if (depth[head[u]] < depth[head[v]]) swap(u, v);
        int h = head[u];
        for (int p = pos[h]; p <= pos[u]; ++p)
            outPos.push_back(p);
        u = parent[h];
    }
    if (depth[u] < depth[v]) swap(u, v);
    for (int p = pos[v] + 1; p <= pos[u]; ++p)
        outPos.push_back(p);
}

// ---------- Hopcroft-Karp ----------
struct HopcroftKarp {
    int nL, nR;
    vector<vector<int>> adj;
    vector<int> dist, pairU, pairV;
    HopcroftKarp(int _nL = 0, int _nR = 0) { init(_nL, _nR); }
    void init(int _nL, int _nR) {
        nL = _nL;
        nR = _nR;
        adj.assign(nL, {});
        pairU.assign(nL, -1);
        pairV.assign(nR, -1);
        dist.assign(nL, 0);
    }
    void addEdge(int u, int v) { adj[u].push_back(v); }
    bool bfs() {
        queue<int> q;
        for (int u = 0; u < nL; u++) {
            if (pairU[u] == -1) {
                dist[u] = 0;
                q.push(u);
            } else
                dist[u] = -1;
        }
        bool reachable = false;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int v : adj[u]) {
                int pu = pairV[v];
                if (pu != -1 && dist[pu] == -1) {
                    dist[pu] = dist[u] + 1;
                    q.push(pu);
                }
                if (pu == -1) reachable = true;
            }
        }
        return reachable;
    }
    bool dfs(int u) {
        for (int v : adj[u]) {
            int pu = pairV[v];
            if (pu == -1 || (dist[pu] == dist[u] + 1 && dfs(pu))) {
                pairU[u] = v;
                pairV[v] = u;
                return true;
            }
        }
        dist[u] = -1;
        return false;
    }
    int maxMatching() {
        int matching = 0;
        while (bfs()) {
            for (int u = 0; u < nL; u++)
                if (pairU[u] == -1)
                    if (dfs(u)) matching++;
        }
        return matching;
    }
};

// ---------- main ----------
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    g.assign(n + 1, {});
    vector<pair<int, int>> edges(n); // 1-based, store input edges for output order (edges[1..n-1])
    for (int i = 1; i <= n - 1; i++) {
        int a, b;
        cin >> a >> b;
        edges[i] = {a, b};
        g[a].push_back({b, i});
        g[b].push_back({a, i});
    }
    parent.assign(n + 1, 0);
    depth.assign(n + 1, 0);
    heavy.assign(n + 1, -1);
    sz.assign(n + 1, 0);
    head.assign(n + 1, 0);
    pos.assign(n + 1, 0);
    edgeIdAtPos.assign(n + 2, -1); // positions 1..n
    curPos = 0;
    depth[1] = 0;
    dfs_sz(1, 0);
    dfs_hld(1, 1, -1);

    // read queries
    int q;
    cin >> q;
    struct Q {
        char type;
        int u, v;
        int x;
        int id;
    };
    vector<Q> queries;
    queries.reserve(q);
    for (int i = 0; i < q; i++) {
        char t;
        int u, v, x;
        cin >> t >> u >> v >> x;
        queries.push_back({t, u, v, x, i});
    }

    // Build segtrees (size = n because pos runs 1..n). Edge positions are pos[child] (not for root)
    SegChMax segL(n + 5);
    SegChMin segU(n + 5);

    // process queries: for each 'm' (lower bound) we do chmax on path edges; for each 'M' (upper bound) chmin on path edges
    for (auto& qu : queries) {
        if (qu.type == 'm') { // min on path = x  -> edges must be >= x and one edge == x  => chmax lower bounds
            update_path_edges(qu.u, qu.v, qu.x, true, segL, segU);
        } else { // 'M' max on path = x -> edges must be <= x and one edge == x => chmin upper bounds
            update_path_edges(qu.u, qu.v, qu.x, false, segL, segU);
        }
    }

    // collect final L and U for each edge (by its pos)
    int mEdges = n - 1;
    vector<int> Lpos(n + 2), Upos(n + 2);
    for (int p = 2; p <= n; ++p) { // pos[root] may be 1; edges are mapped to nodes except root
        Lpos[p] = segL.query_point(p);
        Upos[p] = segU.query_point(p);
    }
    // For safety assign for pos==1 too (unused)
    Lpos[1] = segL.query_point(1);
    Upos[1] = segU.query_point(1);

    // Check consistency: for every edge (pos mapping) L <= U
    bool ok = true;
    for (int p = 2; p <= n; p++) {
        if (Lpos[p] > Upos[p]) {
            ok = false;
            break;
        }
    }
    if (!ok) {
        cout << -1 << '\n';
        return 0;
    }

    // Build adjacency for bipartite matching:
    // left = queries (all q), right = edges (indices 1..mEdges -> we'll remap to 0..mEdges-1)
    HopcroftKarp hk(q, mEdges);
    // For each query, collect positions on path and add an edge to each edge id that can host that query's x
    for (int i = 0; i < q; i++) {
        auto& qu = queries[i];
        vector<int> poslist;
        collect_edge_positions_on_path(qu.u, qu.v, poslist);
        for (int p : poslist) {
            if (p <= 0 || p > n) continue;
            int l = Lpos[p], uval = Upos[p];
            if (l <= qu.x && qu.x <= uval) {
                int eId = edgeIdAtPos[p]; // original edge id (1..n-1)
                if (eId == -1) continue;
                hk.addEdge(i, eId - 1); // map edge id to 0-based
            }
        }
    }

    int matching = hk.maxMatching();
    if (matching < q) {
        cout << -1 << '\n';
        return 0;
    }

    // construct weights for edges
    vector<int> weight(n, 1000000000);
    // for each matched right vertex (edge), hk.pairV[edge] gives query id
    for (int e = 0; e < mEdges; e++) {
        int qid = hk.pairV[e];
        int pos_of_edge = -1;
        // find pos for this edge id: we have edgeIdAtPos[pos] = e+1
        // Instead of searching, build reverse map:
        // Let's build reverse map once:
    }
    // build reverse map pos -> edgeId already edgeIdAtPos; let's build edgeId -> pos
    vector<int> edgePos(mEdges + 1, -1); // 1..mEdges
    for (int p = 1; p <= n; p++) {
        int eid = edgeIdAtPos[p];
        if (eid != -1) edgePos[eid] = p;
    }
    // assign weights for matched edges
    for (int e = 1; e <= mEdges; e++) {
        int matchedQuery = hk.pairV[e - 1];
        int p = edgePos[e];
        if (matchedQuery != -1) {
            weight[e] = queries[matchedQuery].x;
        } else {
            // choose a value inside [Lpos[p], Upos[p]]
            int chosen;
            if (Lpos[p] != -INF)
                chosen = Lpos[p];
            else if (Upos[p] != INF)
                chosen = Upos[p];
            else
                chosen = 1000000000;
            // ensure chosen in interval
            if (chosen < Lpos[p]) chosen = Lpos[p];
            if (chosen > Upos[p]) chosen = Upos[p];
            weight[e] = chosen;
        }
    }

    // print edges in original order: a b weight
    for (int i = 1; i <= mEdges; i++) {
        cout << edges[i].first << ' ' << edges[i].second << ' ' << weight[i] << '\n';
    }

    return 0;
}

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