제출 #956054

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
956054		vjudge1	Min-max tree (BOI18_minmaxtree)	C++17	0 / 100	168 ms	39252 KiB

minmaxtree

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 7e4 + 5;
vector<int> g[N];
int val[N];
vector<int> min_start[N], min_end[N];
vector<int> max_start[N], max_end[N];
multiset<int> mins[N], maxes[N];
int par[N][20], d[N];
void dfs(int c = 1, int p = 0) {
    d[c] = d[p] + 1;
    for (int n : g[c]) {
        if (n == p)
            continue;
        dfs(n, c);
        par[n][0] = c;
        for (int i = 1; i < 20; i++)
            par[n][i] = par[par[n][i - 1]][i - 1];
    }
}

void merge(int c, int ch) {
    if (mins[c].size() < mins[ch].size())
        mins[c].swap(mins[ch]);
    for (int m : mins[ch])
        mins[c].insert(m);
    mins[ch].clear();
    if (maxes[c].size() < maxes[ch].size())
        maxes[c].swap(maxes[ch]);
    for (int m : maxes[ch])
        maxes[c].insert(m);
    maxes[ch].clear();
}

void dfs2(int c = 1, int p = 0) {
    for (int n : g[c]) {
        if (n == p)
            continue;
        dfs2(n, c);
        merge(c, n);
    }
    for (int x : min_start[c])
        mins[c].insert(x);
    for (int x : max_start[c])
        maxes[c].insert(x);

    if (mins[c].size())
        val[c] = *mins[c].rbegin();
    if (maxes[c].size())
        val[c] = *maxes[c].begin();

    // for (int x : min_end[c])
    //     mins[c].erase(mins[c].find(x)), mins[c].erase(mins[c].find(x));
    // for (int x : max_end[c])
    //     maxes[c].erase(maxes[c].find(x)), maxes[c].erase(maxes[c].find(x));
}

int lca(int a, int b) {
    if (d[a] < d[b])
        swap(a, b);
    for (int i = 19; i >= 0; i--) {
        if (d[par[a][i]] >= d[b])
            a = par[a][i];
    }
    if (a == b)
        return a;
    for (int i = 19; i >= 0; i--) {
        if (par[a][i] != par[b][i])
            a = par[a][i], b = par[b][i];
    }
    return par[a][0];
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    for (int i = 0; i + 1 < n; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs();
    int q;
    cin >> q;
    while (q--) {
        char c;
        cin >> c;
        int a, b, v;
        cin >> a >> b >> v;
        int l = lca(a, b);
        auto &st = c == 'M' ? max_start : min_start;
        auto &en = c == 'M' ? max_end : min_end;
        st[a].push_back(v);
        st[b].push_back(v);
        en[l].push_back(v);
    }
    dfs2();
    for (int i = 2; i <= n; i++) {
        cout << i << " " << par[i][0] << " " << val[i] << "\n";
    }
}

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