Submission #1263840

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263840		oloc	Min-max tree (BOI18_minmaxtree)	C++20	29 / 100	129 ms	34488 KiB

minmaxtree

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

struct edge{
    int u;
    int v;
    int w;
};

const int MAXN = 7e4 + 7;
// const int MAXN = 10000;
const int MAXM = 2 * MAXN + 7;
vector<int> graf[MAXN];
vector<int> to_match[MAXM];
vector<int> xs;
vector<pair<int, int>> edges;
map<int, int> num_to_idx;
int match[MAXM];
int vis[MAXM];
// vector<edge> ans;
set<int> maxy[MAXN];
set<int> miny[MAXN];

bool augment(int v){
    // cerr << "v: " << v << '\n';
    vis[v] = 1;
    for(int u : to_match[v]){
        if(match[u] == -1){
            match[u] = v;
            match[v] = u;
            return 1;
        }
    }

    for(int u : to_match[v]){
        if(!vis[match[u]] && augment(match[u])){
            match[u] = v;
            match[v] = u;
            return 1;
        }
    }
    return 0;
}

void matching(){
    while(true){
        bool cos = 0;
        for(int v = 0; v < MAXM; v++) vis[v] = 0;
        for(int v = 0; v < MAXM; v++){
            if(match[v] == -1 && augment(v)){
                cos = 1;
            }
        }
        if(!cos) break;
    }
}

void merge(set<int> &a, set<int> &b){
    if(a.size() < b.size()) swap(a, b);
    while(!b.empty()){
        int elem = *b.begin();
        b.erase(b.begin());
        auto it = a.lower_bound(elem);
        if(it != a.end() && (*it) == elem){
            a.erase(it);
            continue;
        }
        a.insert(elem);
    }
}

// void print_s(set<pair<int, int>> &s){
//     for(auto [x, u] : s) cerr << "(" << x << ", " << u << ") ";
//     cerr << '\n';
// }

void dfs(int v, int prev){
    // cerr << "v: " << v << '\n';
    for(int u : graf[v]){
        if(u != prev) dfs(u, v);
    }

    // cerr << "next v: " << v << '\n';
    // print_s(s[v]);
    for(int u : graf[v]){
        if(u == prev) continue;
        // pair<int, int> elem = {-1, -1};
        int idx_edge = edges.size();
        if(!maxy[u].empty()){
            int idx_x = num_to_idx[*maxy[u].begin()];
            to_match[idx_edge].push_back((idx_x + MAXN));
            to_match[(idx_x + MAXN)].push_back(idx_edge);
        }
        if(!miny[u].empty()){
            auto it = miny[u].end();
            it--;
            int idx_x = num_to_idx[*it];
            to_match[idx_edge].push_back((idx_x + MAXN));
            to_match[(idx_x + MAXN)].push_back(idx_edge);
        }
            // int a = *(maxy[u].begin());
            // to_match[a].push_back(u + MAXN);
            // to_match[u + MAXN].push_back(a);
        // if(!miny[u].empty()){
        //     auto it = miny[u].end();
        //     it--;
        //     int a = (*it).first;
        //     to_match[a].push_back(u + MAXN);
        //     to_match[]
        // }
        // edge ne = {u, v, mini.first};
        edges.push_back({u, v});

        // , elem.first});
        merge(maxy[v], maxy[u]);
        merge(miny[v], miny[u]);
        // merge(miny[v], miny[u]);
    }
    // print_s(s[v]);
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n;
    cin >> n;

    fill(match, match + MAXM, -1);

    for(int i = 0; i < n - 1; i++){
        int u, v;
        cin >> u >> v;
        graf[u].push_back(v);
        graf[v].push_back(u);
    }

    int q;
    cin >> q;
    for(int i = 0; i < q; i++){
        int u, v, m;
        char typ;
        cin >> typ >> u >> v >> m;
        xs.push_back(m);
        num_to_idx[m] = i;
        if(typ == 'M'){
            // cerr << "ok\n";
            maxy[u].insert(m);
            maxy[v].insert(m);
        }
        else{
            miny[u].insert(m);
            miny[v].insert(m);
        }
    }

    dfs(1, -1);
    // cerr << "edges\n";
    // for(int i = 0; i < n - 1; i++){
    //     cerr << i << ' ' << edges[i].first << ' ' << edges[i].second << '\n';
    // }
    // cerr << "--------------\n";

    // cerr << "to_match\n";
    // for(int i = 0; i < n - 1; i++){
    //     cerr << i << " -> ";
    //     for(int u : to_match[i]) cerr << u << ' ' << xs[u - MAXN] << '\n';
    //     cerr << "****************\n";
    // }
    // cerr << "---------------\n";
    
    matching();
    for(int i = 0; i < n - 1; i++){
        cout << edges[i].first << ' ' << edges[i].second << ' ';
        if(match[i] != -1) cout << xs[match[i] - MAXN] << '\n';
        else cout << "0\n";
    }
    // for(auto [u, v, w] : ans){
    //     cout << u << ' ' << v << ' ' << w << '\n';
    // }
}

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