Submission #1267598

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267598		Alebn	Min-max tree (BOI18_minmaxtree)	C++20	22 / 100	415 ms	55676 KiB

minmaxtree

#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
using namespace std;

const int N = 18;
struct LCA {
    int timer;
    vector<vector<int>> graph, up;
    vector<int> in, out;
    LCA(vector<vector<int>>& g):graph(g) {
        timer = 0;
        up = vector<vector<int>>(N, vector<int>(g.size())), in = out = vector<int>(g.size());
        dfs(0, 0);
    }
    void dfs(int i, int p) {
        in[i] = timer;
        timer++;
        up[0][i] = p;
        for(int j = 1; j < N; j++) up[j][i] = up[j - 1][up[j - 1][i]];
        for(auto j : graph[i]) {
            if(j != p) dfs(j, i);
        }
        out[i] = timer;
        timer++;
    }
    bool check(int i, int j) {
        return in[i] <= in[j] && out[j] <= out[i];
    }
    int lca(int i, int j) {
        if(check(i, j)) return i;
        if(check(j, i)) return j;
        for(int x = N - 1; x >= 0; x--) {
            if(!check(up[x][i], j)) i = up[x][i];
        }
        return up[0][i];
    }
};
struct E {
    int x, y, z;
    E(int xi, int yi, int zi):x(xi),y(yi),z(zi){}
    E(){}
};

// SUBTASK 2 : ONLY MAXIMUMS

signed main() {
    int n, x, y, k, temp;
    cin >> n;
    vector<vector<int>> graph(n);
    for(int i = 0; i < n - 1; i++) {
        cin >> x >> y;
        graph[--x].push_back(--y);
        graph[y].push_back(x);
    }
    cin >> k;
    char m;
    LCA lca(graph);
    vector<int> ks(k);
    map<int,bool> odabr;
    vector<vector<int>> delmi(n), delma(n);
    vector<set<int>> stmi(n), stma(n);
    for(int i = 0; i < k; i++) {
        cin >> m >> x >> y >> ks[i];
        if(m == 'M') {
            delma[lca.lca(--x, --y)].push_back(ks[i]);
            stma[x].insert(ks[i]);
            stma[y].insert(ks[i]);
        } else {
            delmi[lca.lca(--x, --y)].push_back(ks[i]);
            stmi[x].insert(ks[i]);
            stmi[y].insert(ks[i]);
        }
        odabr[ks[i]] = false;
    }
    // dfs dp
    vector<E> res;
    res.reserve(n);
    function<void(int,int)> dfs = [&](int i, int p) {
        for(auto j : graph[i]) {
            if(j != p) {
                dfs(j, i);
                // push into st[i]
                if(stma[i].size() < stma[j].size()) swap(stma[i], stma[j]);
                for(auto x : stma[j]) stma[i].insert(x);
                if(stmi[i].size() < stmi[j].size()) swap(stmi[i], stmi[j]);
                for(auto x : stmi[j]) stmi[i].insert(x);
            }
        }
        // apply del[i]
        for(auto x : delma[i]) stma[i].erase(x);
        for(auto x : delmi[i]) stmi[i].erase(x);
        if(i) {
            if(stma[i].size() && stmi[i].size()) {
                // which one to choose??
                x = *stma[i].begin(), y = *stmi[i].rbegin();
                // if one alr chosen, choose the other
                if(odabr[x]) temp = y;
                else temp = x;
            } else if(stma[i].size()) temp = *stma[i].begin();
            else if(stmi[i].size()) temp = *stmi[i].rbegin();
            else temp = 0;
            odabr[temp] = true;
            res.push_back(E(p, i, temp));
        }
    };
    dfs(0,0);
    for(auto i : res) cout << i.x + 1 << " " << i.y + 1 << " " << i.z << "\n";
}

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