Submission #1230224

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230224		Ghulam_Junaid	Min-max tree (BOI18_minmaxtree)	C++20	29 / 100	186 ms	46752 KiB

minmaxtree

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

typedef long long ll;

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

void dfs(ll v){
    for (ll e : g[v]){
        ll 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 (ll j = 1; j < LG; j ++)
            par[u][j] = par[par[u][j - 1]][j - 1];

        dfs(u);
    }
}

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

    if (u == v) return v;

    for (ll 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(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n;
    for (ll 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);
        ans[i] = xx;
    }
    dfs(1);

    cin >> k;
    for (ll i = 0, u, v, w, id; i < k; i ++){
        char c;
        cin >> c >> u >> v >> w;
        id = (c == 'M');
        ll sgn = ((c == 'M') ? 1 : -1);
        ope[id].push_back({w * sgn, {u, v}});
    }
    for (ll 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;
            ll w = abs(wei);
            ll L = lca(u, v);
        
            ll cur = u;
            while (cur != L){
                while (nxt[cur] and h[cur] > h[L]){
                    ll prv = cur;
                    cur = nxt[cur];
                    if (h[nxt[prv]] > h[L]) nxt[prv] = L;
                }
                if (h[cur] <= h[L]) break;

                ll 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]){
                    ll prv = cur;
                    cur = nxt[cur];
                    if (h[nxt[prv]] > h[L]) nxt[prv] = L;
                }
                if (h[cur] <= h[L]) break;

                ll 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<ll, ll>> st1, st2;
    for (ll 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] != xx or ce == 0 or cnt_edge[e] == 0){
            st1.erase(st1.begin());
            continue;
        }
        if (cnt_edge[e] == 1){
            st1.erase(st1.begin());
            ll w = vals[e][0] + vals[e][1];
            ans[e] = w;
            for (ll 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] > 0 and ans[ne] == xx) 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;
        e = -1;
        for (ll ne : appear[w])
            if (ans[ne] == xx and (vals[ne][0] == w or vals[ne][1] == w)) e = ne;
        if (e == -1) continue;
        
        ll o = vals[e][0];
        if (o == w) o = vals[e][1];
        st2.erase({cnt_val[o], o});
        cnt_val[o]--;
        if (cnt_val[o] > 0) st2.insert({cnt_val[o], o});
        vals[e][0] = vals[e][1] = 0;
        cnt_edge[e] = 0;

        ans[e] = w;
        for (ll 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] > 0 and ans[ne] == xx) st1.insert({cnt_edge[ne], ne});
        }
        cnt_val[w] = 0;
    }

    for (ll e = 0; e < n - 1; e ++){
        auto [u, v] = edges[e];
        if (ans[e] == xx) 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