oj.uz

Submission #956053

# Submission time Handle Problem Language Result Execution time Memory
956053 2024-03-31T23:46:38 Z vjudge1 Min-max tree (BOI18_minmaxtree) C++17
0 / 100
 99 ms 59216 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Runtime error 19 ms 38232 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 99 ms 59216 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 64 ms 51280 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Runtime error 19 ms 38232 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -