제출 #145868

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
145868		darkkcyan	Min-max tree (BOI18_minmaxtree)	C++14	100 / 100	489 ms	52344 KiB

minmaxtree

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

#define llong long long 
#define xx first
#define yy second
#define len(x) ((int)x.size())
#define rep(i,n) for (int i = -1; ++ i < n; )
#define rep1(i,n) for (int i = 0; i ++ < n; )
#define all(x) x.begin(), x.end()
// #define rand __rand
// mt19937 rng(chrono::system_clock::now().time_since_epoch().count());  // or mt19937_64
// template<class T = int> T rand(T range = numeric_limits<T>::max()) {
    // return (T)(rng() % range);
// }

#define maxn 70101
#define maxlg 18
int n, k;
vector<int> gr[maxn];
int queries[maxn];
int up[maxlg][maxn];
int depth[maxn];

void dfs(int u, int p) {
    up[0][u] = p;
    depth[u] = depth[p] + 1;
    rep(i, maxlg - 1) up[i + 1][u] = up[i][up[i][u]];
    for (auto v: gr[u]) {
        if (v == p) continue;
        dfs(v, u);
    }
}

int lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    for (int d = depth[u] - depth[v], i = 0; d > 0; d >>= 1, ++i)
        if (d & 1) u = up[i][u];
    if (u == v) return u;
    for (int i = maxlg; i--; ) {
        if (up[i][u] == up[i][v]) continue;
        u = up[i][u];
        v = up[i][v];
    }
    return up[0][u];
}

template<typename T> 
struct bin_lifting_ranges {
    T value[maxlg][maxn];
    function<T(T const&, T const&)> update_func;
    bin_lifting_ranges(const T& init_val, function<T(const T&, const T&)> const& fun)
        : update_func(fun)
    {
        rep(i, maxlg)   
            fill(value[i], value[i] + maxn, init_val);
    }

    void update(int u, int dst_depth, const T& new_value) {
        for (int i = 0, d = depth[u] - dst_depth; d > 0; d >>= 1, ++i) {
            if (~d & 1) continue;
            value[i][u] = update_func(value[i][u], new_value);
            u = up[i][u];
        }
    }

    void propagate() {
        for (int i = maxlg; --i > 0; ) {
            int f = i - 1;
            rep1(u, n) {
                int v = up[f][u];
                value[f][u] = update_func(value[f][u], value[i][u]);
                value[f][v] = update_func(value[f][v], value[i][u]);
            }
        }
    }

    T& operator[](int i) { return value[0][i]; }
};

bin_lifting_ranges<int>
    min_ranges(-1, [](int u, int v) {
        if (u == -1) return v; else if (v == -1) return u;
        return queries[u] > queries[v] ? u : v;
    }),
    max_ranges(-1, [](int u, int v) {
        if (u == -1) return v; else if (v == -1) return u;
        return queries[u] < queries[v] ? u : v;
    });

vector<int> affect_edges[maxn];
set<int> edge_cost[maxn];
bool used[maxn];
void assign_deg_1() {
    queue<int> qu;
    auto push = [&](int cost) {
        if (used[cost]) return ;
        used[cost] = 1;
        qu.push(cost);
    };
    rep1(i, n) if (len(edge_cost[i]) == 1) {
        push(*edge_cost[i].begin());
    }
    for (; len(qu); qu.pop()) {
        int cost = qu.front();
        for (auto v: affect_edges[cost]) {
            if (len(edge_cost[v]) == 1) assert(edge_cost[v].count(cost));
            if (len(edge_cost[v]) < 2) continue;
            edge_cost[v].erase(cost);
            push(*edge_cost[v].begin());
        }
    }
}

set<pair<int, int>> new_gr[maxn];
bool assigned[maxn] = {0};
void assign_deg_2() {
    rep1(i, n) {
        if (len(edge_cost[i]) < 2) continue;
        int u = *edge_cost[i].begin(), v = *edge_cost[i].rbegin();
        new_gr[u].insert({v, i});
        new_gr[v].insert({u, i});
    }
    set<pair<int, int>> prio;
    rep(i, k) {
        prio.insert({len(new_gr[i]), i});
    }

    while (len(prio)) {
        int u = prio.begin()->yy;
        prio.erase(prio.begin());
        assigned[u] = 1;
        auto t = *new_gr[u].begin();
        edge_cost[t.yy].erase(t.xx);
        if (assigned[t.xx]) continue;
        prio.erase({len(new_gr[t.xx]), t.xx});
        new_gr[t.xx].erase({u, t.yy});
        prio.insert({len(new_gr[t.xx]), t.xx});
    }
}

int main(void) {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    rep(i, n - 1) {
        int u, v; cin >> u >> v;
        gr[u].push_back(v);
        gr[v].push_back(u);
    }

    dfs(1, 1);
    cin >> k;
    rep(i, k) {
        char type; int u, v;
        cin >> type >> u >> v >> queries[i];
        int d = depth[lca(u, v)];
        auto& ranges = type == 'm' ? min_ranges : max_ranges;
        ranges.update(u, d, i);
        ranges.update(v, d, i);
    }

    min_ranges.propagate();
    max_ranges.propagate();

    rep1(i, n) {
        for (auto x: {min_ranges[i], max_ranges[i]}) {
            if (x == -1) continue;
            affect_edges[x].push_back(i);
            edge_cost[i].insert(x);
        }
    }

    assign_deg_1();
    assign_deg_2();
    rep1(i, n) {
        if (up[0][i] == i) continue;
        cout << i << ' ' << up[0][i] << ' ';
        // assert(len(edge_cost[i]) != 2);
        if (len(edge_cost[i]) == 0) cout << "0\n";
        else cout << queries[*edge_cost[i].begin()] << '\n';
    }

    return 0;
}

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