Submission #1263465

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263465		anteknne	Min-max tree (BOI18_minmaxtree)	C++20	51 / 100	375 ms	77536 KiB

minmaxtree

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define st first
#define nd second
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define debug true

const int MAXN = 70 * 1000 + 17;
const int MAXLOG = 18;
const int INF = 200 * 1000;
vector<int> graf[MAXN];
vector<int> dodaj[MAXN];
vector<int> usun[MAXN];
vector<int> dodaj2[MAXN];
vector<int> usun2[MAXN];
int pam[MAXN][MAXLOG];
int lev[MAXN];
map<pii, int> wyn;
map<pii, int> wyn2;
set<pair<int, int>> pq;
vector<int> graf2[MAXN * 2];
pii kod[2 * MAXN];
map<int, bool> jest;
map<pii, int> kodr;
map<int, int> kodr2;
map<pii, int> fin;
int macz[MAXN * 2];
bool odw[2 * MAXN];

void DFS (int v, int o) {
    pam[v][0] = o;
    for (int i = 1; i < MAXLOG; i++) {
        pam[v][i] = pam[pam[v][i - 1]][i - 1];
    }
    for (auto x : graf[v]) {
        if (x != o) {
            lev[x] = lev[v] + 1;
            DFS (x, v);
        }
    }
}

int LCA (int a, int b) {
    if (lev[a] < lev[b]) {
        swap(a, b);
    }
    int pot = (1 << (MAXLOG - 1));
    for (int i = MAXLOG - 1; i >= 0; i--) {
        if (lev[a] - pot >= lev[b]) {
            a = pam[a][i];
        }
        pot /= 2;
    }
    if (a == b) {
        return a;
    }
    for (int i = MAXLOG - 1; i >= 0; i--) {
        if (pam[a][i] != pam[b][i]) {
            a = pam[a][i];
            b = pam[b][i];
        }
    }
    return pam[a][0];
}

pair<set<int>*, set<int>*> DFS2 (int v, int o) {
    auto* ms = new set<int>();
    auto* ms2 = new set<int>();

    for (auto x : dodaj[v]) {
        ms->insert(x);
    }
    for (auto x : dodaj2[v]) {
        ms2->insert(x);
    }
    for (auto x : graf[v]) {
        if (x != o) {
            auto el = DFS2(x, v);
            auto nms = el.st;
            if (int(nms->size()) > int(ms->size())) {
                swap(nms, ms);
            }
            for (auto x : *nms) {
                ms->insert(x);
            }


            auto nms2 = el.nd;
            if (int(nms2->size()) > int(ms2->size())) {
                swap(nms2, ms2);
            }
            for (auto x : *nms2) {
                ms2->insert(x);
            }
        }
    }

    for (auto x : usun[v]) {
        ms->erase(x);
    }

    for (auto x : usun2[v]) {
        ms2->erase(x);
    }

    if (v != o) {
        if (int(ms->size()) >= 1) {
            wyn[{v, o}] = *ms->begin();
            fin[{v, o}] = *ms->begin();
        } else {
            wyn[{v, o}] = -1;
            fin[{v, o}] = max(fin[{v, o}], 0);
        }

        if (int(ms2->size()) >= 1) {
            wyn2[{v, o}] = *ms2->begin();
            fin[{v, o}] = *ms2->begin();
        } else {
            wyn2[{v, o}] = -1;
            fin[{v, o}] = max(fin[{v, o}], 0);
        }
    }

    return {ms, ms2};
}

int n;
int nr;

bool powieksz (int u) {
    odw[u] = true;
    for (auto v : graf2[u]) {
        if (macz[v] == 0) {
            macz[v] = u;
            macz[u] = v;
            return true;
        }
    }

    for (auto v : graf2[u]) {
        if(!odw[macz[v]] && powieksz(macz[v])) {
            macz[v] = u;
            macz[u] = v;
            return true;
        }
    }
    return false;
 }

int main () {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n;

    int a, b;
    for (int i = 0; i < n - 1; i ++) {
        cin >> a >> b;
        graf[a].pb(b);
        graf[b].pb(a);
    }

    DFS(1, 1);

    int q;
    cin >> q;
    char c;
    int w;
    for (int i = 0; i < q; i ++) {
        cin >> c >> a >> b >> w;
        if (c == 'M') {
            dodaj[a].pb(w);
            dodaj[b].pb(w);
            usun[LCA(a, b)].pb(w);
        } else {
            dodaj2[a].pb(w);
            dodaj2[b].pb(w);
            usun2[LCA(a, b)].pb(w);
        }
    }

    DFS2(1, 1);

    nr = 0;
    for (auto x : wyn) {
        nr ++;
        kod[nr] = x.st;
        kodr[x.st] = nr;
    }

    int S = nr;

    for (auto x : wyn) {
        if (x.nd == -1) {
            continue;
        }
        if (!jest[x.nd]) {
            jest[x.nd] = true;
            nr ++;
            kod[nr] = {x.nd, -1};
            kodr2[x.nd] = nr;
        }
        graf2[kodr[x.st]].pb(kodr2[x.nd]);
        graf2[kodr2[x.nd]].pb(kodr[x.st]);
    }

    for (auto x : wyn2) {
        if (x.nd == -1) {
            continue;
        }
        if (!jest[x.nd]) {
            jest[x.nd] = true;
            nr ++;
            kod[nr] = {x.nd, -1};
            kodr2[x.nd] = nr;
        }
        graf2[kodr[x.st]].pb(kodr2[x.nd]);
        graf2[kodr2[x.nd]].pb(kodr[x.st]);
    }

    while (true) {
        for (int i = 1; i <= nr; i ++) {
            odw[i] = false;
        }

        bool any = false;
        for (int i = 1; i <= nr; i ++) {
            if (macz[i] == 0 && powieksz(i)) {
                any = true;
            }
        }

        if (!any) {
            break;
        }
    }

    /*for (int i = 1; i <= nr; i ++) {
        cout << i << ": " << macz[i] << "\n";
    }*/

    for (int i = 1; i <= S; i ++) {
        if (macz[i] != 0) {
            fin[kod[i]] = kod[macz[i]].st;
        }
    }


    for (auto x : fin) {
        cout << x.st.st << " " << x.st.nd << " " << x.nd << "\n";
    }


    /*for (int i = 0; i <= nr; i ++) {
        cout << i << ": ";
        for (auto x : graf2[i]) {
            cout << x << " ";
        }
        cout << "\n";
    }*/

    return 0;
}

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