Submission #1259285

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

minmaxtree

#include <bits/stdc++.h>
using namespace std;
#define el '\n'

const int MAXN = 70005;
const int NEG_INF = -1000000000;
const int INF = 1000000000;

struct Query {
    bool type; // 1 for 'M' (max), 0 for 'm' (min)
    int u, v;
    int w;
    Query(char x='#', int U=0, int V=0, int W=0) {
        type = (x == 'M' ? 1 : 0);
        u = U; v = V; w = W;
    }
};

int n, q;
vector<int> graph[MAXN];
vector<Query> queryv; // 1..q
int uID[MAXN], vID[MAXN]; // original edges in input order

// ------------ Hopcroft-Karp (kept your structure) --------------
struct Hopcorft {
    int nL, nR;
    vector<vector<int>> graph;      // adjacency left -> list of right indices
    vector<int> matchLeft, matchRight;
    vector<int> distancia;
    Hopcorft(int l = 0, int r = 0) { init(l,r); }
    void init(int l, int r) {
        nL = l; nR = r;
        graph.assign(nL+1, {});
        matchLeft.assign(nL+1, 0);
        matchRight.assign(nR+1, 0);
        distancia.assign(nL+1, 0);
    }
    void addEdge(int u, int v) { // u in [1..nL], v in [1..nR]
        if (u<=0 || v<=0) return;
        graph[u].push_back(v);
    }
    bool bfs() {
        queue<int> qu;
        for (int u=1; u<=nL; ++u) {
            if (!matchLeft[u]) { distancia[u] = 0; qu.push(u); }
            else distancia[u] = INF;
        }
        distancia[0] = INF;
        while (!qu.empty()) {
            int u = qu.front(); qu.pop();
            if (distancia[u] >= distancia[0]) continue;
            for (int v : graph[u]) {
                int paired = matchRight[v]; // left index matched to v or 0
                if (distancia[paired] == INF) {
                    distancia[paired] = distancia[u] + 1;
                    qu.push(paired);
                }
            }
        }
        return (distancia[0] != INF);
    }
    bool dfs(int u) {
        if (!u) return true;
        for (int v : graph[u]) {
            if (distancia[ matchRight[v] ] == distancia[u] + 1 && dfs(matchRight[v])) {
                matchRight[v] = u;
                matchLeft[u] = v;
                return true;
            }
        }
        distancia[u] = INF;
        return false;
    }
    int maxMatching() {
        int match = 0;
        while (bfs()) {
            for (int u=1; u<=nL; ++u)
                if (!matchLeft[u] && dfs(u)) match++;
        }
        return match;
    }
    // write matched query weights into res[edge_id]
    void getW(vector<int> &res) {
        maxMatching();
        for (int u=1; u<=nL; ++u) {
            if (matchLeft[u]) {
                int e = matchLeft[u];          // matched edge id (right side)
                res[e] = queryv[u].w;         // query index u matched to edge e
            }
        }
    }
};

// ---------- events for sweepline (store w,type,id) ----------
struct Ev { int w; int type; int id; };
vector<Ev> eventA[MAXN], eventR[MAXN]; // index by HLD position

inline void rangeAddEvent(int l, int r, int w, int type, int id) {
    if (l > r) return;
    eventA[l].push_back({w,type,id});
    eventR[r].push_back({w,type,id});
}

// ----------------- HLD -----------------
int timedfs = 1, curChain = 1, edgecnt = 0;
int eID[MAXN];      // eID[u] = edge id for parent[u]-u (0 for root)
int parentArr[MAXN];
int pos[MAXN], arrPos[MAXN];

namespace HeavyLight {
    vector<int> chainHead, chainID;
    vector<int> depth, sz;

    void dfs(int u, int pre) {
        parentArr[u] = pre;
        for (int v : graph[u]) if (v != pre) {
            depth[v] = depth[u] + 1;
            dfs(v,u);
            sz[u] += sz[v];
        }
    }

    void HLD(int u, int pre) {
        if (!chainHead[curChain]) chainHead[curChain] = u;
        chainID[u] = curChain;
        pos[u] = timedfs;
        arrPos[timedfs] = u;
        timedfs++;

        if (u == pre) eID[u] = 0; // root sentinel (we keep parent[root]=root)
        else eID[u] = ++edgecnt;

        int nxt = -1;
        for (int v : graph[u]) if (v != pre) {
            if (nxt == -1 || sz[v] > sz[nxt]) nxt = v;
        }
        if (nxt != -1) HLD(nxt, u);
        for (int v : graph[u]) if (v != pre && v != nxt) {
            curChain++;
            HLD(v, u);
        }
    }

    // add path events using positions
    void addEvent(int u, int v, int w, int type, int id) {
        while (chainHead[chainID[u]] != chainHead[chainID[v]]) {
            if (depth[chainHead[chainID[u]]] < depth[chainHead[chainID[v]]]) swap(u,v);
            int L = pos[ chainHead[ chainID[u] ] ];
            int R = pos[u];
            rangeAddEvent(L, R, w, type, id);
            u = parentArr[ chainHead[ chainID[u] ] ];
        }
        if (depth[u] < depth[v]) swap(u,v);
        if (u != v) {
            // we need edges under v..u, which map to positions pos[v]+1 .. pos[u]
            rangeAddEvent(pos[v] + 1, pos[u], w, type, id);
        }
    }

    void initHLD() {
        chainHead.assign(n+2, 0);
        chainID.assign(n+2, 0);
        depth.assign(n+2, 0);
        sz.assign(n+2, 1);
        // keep parent[root]=root sentinel
        dfs(1, 1);
        HLD(1, 1);
    }
}
using namespace HeavyLight;

// ---------------- input ----------------
void readInput() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i=1;i<n;i++){
        int u,v; cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
        uID[i] = u; vID[i] = v;
    }
    cin >> q;
    queryv.resize(q+1);
    for (int i=1;i<=q;i++){
        char c; int u,v,w; cin >> c >> u >> v >> w;
        queryv[i] = Query(c,u,v,w);
    }
}

// ---------------- solve ----------------
int main(){
    readInput();

    initHLD();

    // build events (use query index as id)
    for (int i=1;i<=q;i++){
        addEvent(queryv[i].u, queryv[i].v, queryv[i].w, queryv[i].type, i);
    }

    // per-edge info
    vector<int> loVal(edgecnt+1, NEG_INF), hiVal(edgecnt+1, INF);
    vector<int> loId(edgecnt+1, 0), hiId(edgecnt+1, 0);

    // active sets store (w,id)
    multiset<pair<int,int>> activeMin, activeMax;

    // sweep positions 1..n
    for (int cur = 1; cur <= n; ++cur) {
        // add events starting here
        for (auto &ev : eventA[cur]) {
            if (ev.type) activeMax.insert({ev.w, ev.id}); // M queries -> activeMax
            else         activeMin.insert({ev.w, ev.id}); // m queries -> activeMin
        }

        int u = arrPos[cur];
        int e = eID[u]; // if 0 skip (root)
        if (e) {
            if (!activeMax.empty()) {
                auto it = activeMax.begin(); // smallest max constraint
                if (it->first < hiVal[e]) { hiVal[e] = it->first; hiId[e] = it->second; }
            }
            if (!activeMin.empty()) {
                auto it = prev(activeMin.end()); // largest min constraint
                if (it->first > loVal[e]) { loVal[e] = it->first; loId[e] = it->second; }
            }
        }

        // remove events ending here
        for (auto &ev : eventR[cur]) {
            if (ev.type) {
                auto it = activeMax.find({ev.w, ev.id});
                if (it != activeMax.end()) activeMax.erase(it);
            } else {
                auto it = activeMin.find({ev.w, ev.id});
                if (it != activeMin.end()) activeMin.erase(it);
            }
        }
    }

    // Build matching graph: Left = queries 1..q, Right = edges 1..edgecnt
    Hopcorft karp(q, edgecnt);
    for (int e=1; e<=edgecnt; ++e) {
        if (loId[e]) karp.addEdge(loId[e], e);
        if (hiId[e] && hiId[e] != loId[e]) karp.addEdge(hiId[e], e);
    }

    // default assign per-edge value within [loVal, hiVal]
    vector<int> res(edgecnt+1, 0);
    for (int e=1;e<=edgecnt;++e) {
        int val = 0;
        if (loVal[e] != NEG_INF) val = max(val, loVal[e]);
        if (hiVal[e] != INF) val = min(val, hiVal[e]);
        // if inconsistent (lo > hi), we still put something; judge problem usually guarantees feasibility
        res[e] = val;
    }

    // run matching and overwrite matched edges with exact query w
    karp.getW(res);

    // map edges to input order: normalize endpoints
    auto norm = [](int a,int b)->pair<int,int>{ if (a>b) swap(a,b); return {a,b}; };
    unordered_map<long long,int> toEID;
    toEID.reserve(edgecnt*2);
    auto key = [](int a,int b)->long long { if (a>b) swap(a,b); return ( (long long)a<<32 ) ^ (long long)b; };
    for (int v=2; v<=n; ++v) {
        int u = parentArr[v];
        toEID[key(u,v)] = eID[v];
    }

    // print in the original input order
    for (int i=1;i<n;i++){
        int a = uID[i], b = vID[i];
        int e = toEID[key(a,b)];
        cout << a << ' ' << b << ' ' << res[e] << el;
    }
    return 0;
}

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