제출 #1227894

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1227894		Ghulam_Junaid	Min-max tree (BOI18_minmaxtree)	C++20	29 / 100	179 ms	35248 KiB

minmaxtree

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

const int N = 7e4 + 10, LG = 18;
int n, k, h[N], par[N][LG], par_edge[N], nxt[N], cnt_edge[N], vals[N][2], ans[N];
vector<int> g[N];
map<int, vector<int>> appear;
map<int, int> cnt_val;
vector<pair<int, int>> edges;
vector<pair<int, pair<int, int>>> ope[2];

void dfs(int v){
    for (int e : g[v]){
        int u = edges[e].first + edges[e].second - v;
        if (u == par[v][0]) continue;

        h[u] = h[v] + 1;
        par_edge[u] = e;
        par[u][0] = v;
        for (int j = 1; j < LG; j ++)
            par[u][j] = par[par[u][j - 1]][j - 1];

        dfs(u);
    }
}

int lca(int u, int v){
    if (h[u] > h[v]) swap(u, v);
    int d = h[v] - h[u];
    for (int i = 0; i < LG; i ++)
        if ((1 << i) & d)
            v = par[v][i];

    if (u == v) return v;

    for (int i = LG - 1; i >= 0; i --)
        if (par[v][i] != par[u][i])
            v = par[v][i], u = par[u][i];

    return par[v][0];
}

int main(){
    memset(ans, -1, sizeof ans);
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

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

    cin >> k;
    for (int i = 0, u, v, w, id; i < k; i ++){
        char c;
        cin >> c >> u >> v >> w;
        id = (c == 'M');
        int sgn = ((c == 'M') ? 1 : -1);
        ope[id].push_back({w * sgn, {u, v}});
    }
    for (int id : {0, 1}){
        sort(ope[id].begin(), ope[id].end());
        memset(nxt, 0, sizeof nxt);
        
        for (auto [wei, P] : ope[id]){
            auto [u, v] = P;
            int w = abs(wei);
            int L = lca(u, v);
        
            int cur = u;
            while (cur != L){
                while (nxt[cur] and h[cur] > h[L]){
                    int prv = cur;
                    cur = nxt[cur];
                    if (h[nxt[prv]] > h[L]) nxt[prv] = L;
                }
                if (h[cur] <= h[L]) break;

                int e = par_edge[cur];
                cnt_edge[e]++;
                vals[e][id] = w;
                nxt[cur] = L;
                cur = par[cur][0];
                appear[w].push_back(e);
                cnt_val[w]++;
            }

            cur = v;
            while (cur != L){
                while (nxt[cur] and h[cur] > h[L]){
                    int prv = cur;
                    cur = nxt[cur];
                    if (h[nxt[prv]] > h[L]) nxt[prv] = L;
                }
                if (h[cur] <= h[L]) break;

                int e = par_edge[cur];
                cnt_edge[e]++;
                vals[e][id] = w;
                nxt[cur] = L;
                cur = par[cur][0];
                appear[w].push_back(e);
                cnt_val[w]++;
            }
        }
    }

    set<pair<int, int>> st1, st2;
    for (int e = 0; e < n - 1; e ++)
        if (cnt_edge[e])
            st1.insert({cnt_edge[e], e});
    for (auto [w, c] : cnt_val)
        st2.insert({c, w});

    while (!st1.empty() and !st2.empty()){
        auto [ce, e] = *st1.begin();
        if (ans[e] != -1 or ce == 0){
            st1.erase(st1.begin());
            continue;
        }
        if (ce == 1){
            st1.erase(st1.begin());
            int w = vals[e][0] + vals[e][1];
            ans[e] = w;
            for (int ne : appear[w]){
                if (vals[ne][0] != w and vals[ne][1] != w) continue;

                if (vals[ne][0] == w) vals[ne][0] = 0;
                if (vals[ne][1] == w) vals[ne][1] = 0;
                st1.erase({cnt_edge[ne], ne});
                cnt_edge[ne]--;
                if (cnt_edge[ne] and ans[ne] == -1) st1.insert({cnt_edge[ne], ne});
            }
            cnt_val[w] = 0;
            continue;
        }
        auto [c, w] = *st2.begin();
        st2.erase(st2.begin());
        if (cnt_val[w] == 0)
            continue;
        for (int ne : appear[w])
            if (ans[ne] == -1) e = ne;
        
        int o = vals[e][0];
        if (o == w) o = vals[e][1];
        st2.erase({cnt_val[o], o});
        cnt_val[o]--;
        st2.insert({cnt_val[o], o});

        ans[e] = w;
        for (int ne : appear[w]){
            if (vals[ne][0] != w and vals[ne][1] != w) continue;

            if (vals[ne][0] == w) vals[ne][0] = 0;
            if (vals[ne][1] == w) vals[ne][1] = 0;
            st1.erase({cnt_edge[ne], ne});
            cnt_edge[ne]--;
            if (cnt_edge[ne] and ans[ne] == -1) st1.insert({cnt_edge[ne], ne});
        }
        cnt_val[w] = 0;
    }

    for (int e = 0; e < n - 1; e ++){
        auto [u, v] = edges[e];
        if (ans[e] <= 0) ans[e] = 1;
        cout << u << " " << v << " " << ans[e] << '\n'; 
    }
}

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