제출 #977744

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
977744		alexdd	Min-max tree (BOI18_minmaxtree)	C++17	100 / 100	154 ms	31080 KiB

minmaxtree

#include<bits/stdc++.h>
using namespace std;
int n,k;
vector<int> con_cuplaj[140005];
int tole[140005],tori[140005];
void add_edge(int xle, int xri)
{
    con_cuplaj[xle].push_back(xri);
    con_cuplaj[xri].push_back(xle);
}
int visited[140005],pas;
bool cupleaza(int nod)
{
    if(visited[nod]==pas)
        return 0;
    visited[nod]=pas;
    for(auto x:con_cuplaj[nod])
    {
        if(tole[x]==0)
        {
            tori[nod]=x;
            tole[x]=nod;
            return 1;
        }
    }
    for(auto x:con_cuplaj[nod])
    {
        if(cupleaza(tole[x]))
        {
            tori[nod]=x;
            tole[x]=nod;
            return 1;
        }
    }
    return 0;
}
void cuplaj()
{
    while(1)
    {
        pas++;
        bool bl=0;
        for(int i=1;i<=k;i++)
            if(tori[i]==0)
                bl |= cupleaza(i);
        if(!bl)
            break;
    }
}

vector<int> con[70005];
pair<int,int> lim[70005];
pair<int,int> care[70005];
int val[70005];
vector<pair<pair<int,int>,int>> baga[70005];
vector<pair<pair<int,int>,int>> scoate[70005];

int parent[70005];
int depth[70005];
int head[70005];
int pos[70005],curpos;
int siz[70005];
int ord[70005];

void dfs_init(int nod)
{
    siz[nod]=1;
    for(auto adj:con[nod])
    {
        if(adj!=parent[nod])
        {
            parent[adj] = nod;
            depth[adj] = depth[nod]+1;
            dfs_init(adj);
            siz[nod] += siz[adj];
        }
    }
}
void decomp(int nod, int chead)
{
    pos[nod]=++curpos;
    ord[pos[nod]]=nod;
    head[nod]=chead;
    int maxc=-1,heavy=-1;
    for(auto adj:con[nod])
    {
        if(adj!=parent[nod] && siz[adj]>maxc)
        {
            maxc=siz[adj];
            heavy=adj;
        }
    }
    if(heavy!=-1)
        decomp(heavy,chead);
    for(auto adj:con[nod])
        if(adj!=parent[nod] && adj!=heavy)
            decomp(adj,adj);
}
void add_val(int le, int ri, pair<pair<int,int>,int> newv)
{
    if(le>ri)
        return;
    baga[le].push_back(newv);
    scoate[ri+1].push_back(newv);
}
void add_hld(int a, int b, pair<pair<int,int>,int> newv)
{
    for(;head[a]!=head[b];b=parent[head[b]])
    {
        if(depth[head[a]]>depth[head[b]])
            swap(a,b);
        add_val(pos[head[b]],pos[b],newv);
    }
    if(pos[a]>pos[b])
        swap(a,b);
    add_val(pos[a]+1,pos[b],newv);
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    int a,b,c;
    for(int i=1;i<n;i++)
    {
        cin>>a>>b;
        con[a].push_back(b);
        con[b].push_back(a);
    }
    dfs_init(1);
    decomp(1,1);
    cin>>k;
    char ch;
    for(int i=1;i<=k;i++)
    {
        cin>>ch>>a>>b>>c;
        val[i]=c;
        if(ch=='M')
        {
            add_hld(a,b,{{c,i},1});
        }
        else
        {
            add_hld(a,b,{{c,i},0});
        }
    }
    set<pair<int,int>> s[2];
    for(int i=1;i<=n;i++)
    {
        for(auto x:scoate[i]) s[x.second].erase({x.first});
        for(auto x:baga[i]) s[x.second].insert({x.first});
        if(s[0].empty())
        {
            lim[ord[i]].first = -1;
            care[ord[i]].first = -1;
        }
        else
        {
            lim[ord[i]].first = (*prev(s[0].end())).first;
            care[ord[i]].first = (*prev(s[0].end())).second;
        }
        if(s[1].empty())
        {
            lim[ord[i]].second = -1;
            care[ord[i]].second = -1;
        }
        else
        {
            lim[ord[i]].second = (*s[1].begin()).first;
            care[ord[i]].second = (*s[1].begin()).second;
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(care[i].first != -1) add_edge(care[i].first, k+i);
        if(care[i].second != -1) add_edge(care[i].second, k+i);
    }
    cuplaj();
    for(int i=2;i<=n;i++)
    {
        cout<<i<<" "<<parent[i]<<" ";
        if(tole[k+i]==0)
        {
            if(lim[i].first!=-1) cout<<lim[i].first<<"\n";
            else if(lim[i].second!=-1) cout<<lim[i].second<<"\n";
            else cout<<1<<"\n";
        }
        else
        {
            cout<<val[tole[k+i]]<<"\n";
        }
    }
    return 0;
}

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