제출 #1270309

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1270309		BigBadBully	Min-max tree (BOI18_minmaxtree)	C++20	22 / 100	283 ms	59532 KiB

minmaxtree

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>

#define ff first
#define ss second
const int inf = 2e9;
using namespace std;
using ld = long double;

void solve()
{
    int n;
    cin >> n;
    vector<vector<int>> graph(n);
    for (int i = 1; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        graph[--a].push_back(--b);
        graph[b].push_back(a);
    }
    vector<int> tura,pos(n),depth(n,-1);
    function<void(int,int)> eul = [&](int cur,int prev)
    {
        depth[cur] = depth[prev]+1;
        pos[cur] = tura.size();
        tura.push_back(cur);
        for(int a : graph[cur])
            if (a!=prev)
                eul(a,cur),tura.push_back(cur);
    };
    eul(0,0);
    auto cmp = [&](int a,int b)->int
    {
        if (depth[a] <= depth[b])return a;
        return b;
    };
    int sz = tura.size();
    vector<vector<int>> sp(20,vector<int>(sz));
    sp[0] = tura;
    for (int bit = 1; bit < 20; bit++)
        for (int i = 0; i+(1<<bit-1) < sz; i++)
            sp[bit][i] = cmp(sp[bit-1][i],sp[bit-1][i+(1<<bit-1)]);
    auto query = [&](int l,int r)
    {
        l = pos[l],r = pos[r];
        if(l>r)swap(l,r);
        if (l==r)return sp[0][l];
        int lgg = __lg(r-l+1);
        return cmp(sp[lgg][l],sp[lgg][r-(1<<lgg)+1]);
    };
    int k;
    cin >> k;
    array<vector<pair<int, pii>>, 2> al;
    for (int i = 0; i < k; i++)
    {
        char ch;
        cin >> ch;
        int p = 0;
        if (ch != 'M')
            p = 1;
        int a, b, c;
        cin >> a >> b >> c;
        al[p].push_back({c, {--a, --b}});
    }
    for (int p = 0; p < 2; p++)
        sort(al[p].begin(), al[p].end());
    reverse(al[1].begin(),al[1].end());
    vector<array<int,2>> pr(n,{inf,-inf});
    vector<int> par(n);
    for (int put = 0; put < 2; put++)
    {
        vector<int> del(n);
        for(int i = 0; i < n; i++)del[i] = i;
        
        function<void(int, int)> dfs = [&](int cur, int prev)
        {
            for (int a : graph[cur])
                if (a != prev)
                    dfs(a, cur);
            par[cur] = prev;
        };
        dfs(0, inf);
        function<int(int)> fnd = [&](int x)
        {
            if(x == inf || del[x] == x)
                return x;
            return del[x] = fnd(del[x]);
        };
        for(auto a : al[put])
        {
            int l = a.ss.ff,r = a.ss.ss;
            int lca = query(l,r);
            l = fnd(l),r = fnd(r);
            for(int it = 0;it < 2; it++,l = r)
            while(l<inf && depth[l] > depth[lca])
            {
                pr[l][put] = a.ff;
                del[l] = fnd(par[l]);
                l = fnd(l);
            }
        }
    }
    vector<int> ans(n,inf);
    map<int,set<pii>> g;
    for (int i = 1; i < n; i++)
        g[pr[i][0]].insert({pr[i][1],i}),
        g[pr[i][1]].insert({pr[i][0],i});
    set<pii> minis;
    for (auto a : g)
        if (abs<int>(a.ff)!=inf)
        minis.insert({a.ss.size(),a.ff});
    auto del = [&](int i)
    {
        int a = pr[i][0];
        int b = pr[i][1];
        if(minis.find({g[a].size(),a})!=minis.end())
        minis.erase({g[a].size(),a});
        if(minis.find({g[b].size(),b})!=minis.end())
        minis.erase({g[b].size(),b});
        g[a].erase({b,i}),
        g[b].erase({a,i});
        if(g[a].size()>0 && abs<int>(a)<inf)
        minis.insert({g[a].size(),a});
        if(g[b].size()>0&& abs<int>(b)<inf)
        minis.insert({g[b].size(),b});
    };

    while(minis.size())
    {
        auto fr = (*minis.begin()).ss;
        int idx = (*g[fr].begin()).ss;
        if(ans[idx]==inf)
        ans[idx] = fr;
        del(idx);
    }
    for (int i =1 ; i < n; i++)
        cout << i+1 << ' ' << par[i]+1 << ' ' << ans[i] << '\n';
}

signed main()
{
    ios::sync_with_stdio(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
}

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