Submission #226793

#	Time	Username	Problem	Language	Result	Execution time	Memory
226793		Andrei_Cotor	Min-max tree (BOI18_minmaxtree)	C++11	36 / 100	820 ms	262148 KiB

minmaxtree

#include<fstream>
#include<iostream>
#include<vector>
#include<set>
#include<map>
 
using namespace std;
 
vector<int> Adj[70005];
vector<pair<int,int> > Min[70005],Max[70005];
int Niv[70005],P[20][70005];
 
int getlca(int x, int y)
{
    if(Niv[x]>Niv[y])
        swap(x,y);
 
    for(int i=16; i>=0; i--)
    {
        if(Niv[P[i][y]]>=Niv[x])
            y=P[i][y];
    }
 
    if(x==y)
        return x;
 
    for(int i=16; i>=0; i--)
    {
        if(P[i][x]!=P[i][y])
        {
            x=P[i][x];
            y=P[i][y];
        }
    }
 
    return P[0][x];
}
 
void dfs(int nod, int p)
{
    Niv[nod]=1+Niv[p];
    P[0][nod]=p;
    for(auto other:Adj[nod])
    {
        if(other==p)
            continue;
        dfs(other,nod);
    }
}
 
int Mini[70005],Maxi[70005]; //val minima si maxima pe care o poate avea muchia
set<int> Smin[70005],Smax[70005];
int HPath[70005],Sz[70005],nr;
 
void getMaxiMini(int nod, int p)
{
    Sz[nod]=1;
    int mx=0;
    for(auto other:Adj[nod])
    {
        if(other==p)
            continue;
 
        getMaxiMini(other,nod);
 
        if(Sz[other]>Sz[mx])
            mx=other;
    }
 
    if(mx==0)
        HPath[nod]=++nr;
    else
        HPath[nod]=HPath[mx];
 
    for(auto other:Adj[nod])
    {
        if(other==p || other==mx)
            continue;
 
        for(auto el:Smin[HPath[other]])
            Smin[HPath[nod]].insert(el);
 
        for(auto el:Smax[HPath[other]])
            Smax[HPath[nod]].insert(el);
    }
 
    for(auto el:Min[nod])
    {
        if(el.second==-1)
            Smin[HPath[nod]].erase(el.first);
        else
            Smin[HPath[nod]].insert(el.first);
    }
 
    for(auto el:Max[nod])
    {
        if(el.second==-1)
            Smax[HPath[nod]].erase(el.first);
        else
            Smax[HPath[nod]].insert(el.first);
    }
 
    if(!Smin[HPath[nod]].empty())
        Mini[nod]=*Smin[HPath[nod]].rbegin();
 
    if(!Smax[HPath[nod]].empty())
        Maxi[nod]=*Smax[HPath[nod]].begin();
}
 
vector<int> G[70005];
int Edge[70005],Value[70005];
int Viz[70005];
 
bool potr(int nod)
{
    if(Viz[nod])
        return 0;
    
    Viz[nod]=1;
    for(auto edge:G[nod])
    {
        if(!Value[edge])
        {
            Value[edge]=nod;
            Edge[nod]=edge;
            return 1;
        }
    }
 
    for(auto edge:G[nod])
    {
        if(potr(Value[edge]))
        {
            Value[edge]=nod;
            Edge[nod]=edge;
            return 1;
        }
    }
    return 0;
}
 
map<int,int> Ind;
int Rez[70005];
 
int main()
{
	ios::sync_with_stdio(false);
  	cin.tie(0);
  	cout.tie(0);
    int n;
    cin>>n;
    for(int i=1; i<n; i++)
    {
        int x,y;
        cin>>x>>y;
 
        Adj[x].push_back(y);
        Adj[y].push_back(x);
    }
 
    dfs(1,0);
    for(int i=1; i<=16; i++)
    {
        for(int j=1; j<=n; j++)
        {
            P[i][j]=P[i-1][P[i-1][j]];
        }
    }
            
    int m;
    cin>>m;
    for(int i=1; i<=m; i++)
    {
        char tip;
        int x,y,val;
        cin>>tip>>x>>y>>val;
 
        if(tip=='m')
        {
            int lca=getlca(x,y);
 
            if(x!=lca)
                Min[x].push_back({val,1});
            if(y!=lca)
                Min[y].push_back({val,1});
            Min[lca].push_back({val,-1});
        }
        else
        {
            int lca=getlca(x,y);
 
            if(x!=lca)
                Max[x].push_back({val,1});
            if(y!=lca)
                Max[y].push_back({val,1});
            Max[lca].push_back({val,-1});
        }
 
        Ind[val]=i;
    }
 
    getMaxiMini(1,0);
 
    for(int i=2; i<=n; i++)
    {
        if(Mini[i]!=0)
            G[Ind[Mini[i]]].push_back(i);
 
        if(Maxi[i]!=0)
            G[Ind[Maxi[i]]].push_back(i);
    }
 
    bool cont=1;
    while(cont)
    {
        cont=0;
        for(int i=1; i<=m; i++)
            Viz[i]=0;
 
        for(int i=1; i<=m; i++)
        {
            if(!Edge[i])
                cont|=potr(i);
        }
    }
 
    for(auto el:Ind)
    {
        Rez[Edge[el.second]]=el.first;
    }
 
    for(int i=2; i<=n; i++)
    {
        cout<<i<<" "<<P[0][i]<<" ";
 
        if(Rez[i])
            cout<<Rez[i]<<"\n";
        else
            cout<<Mini[i]<<"\n";
    }
    return 0;
}

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