제출 #209320

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
209320		Nashik	Min-max tree (BOI18_minmaxtree)	C++14	100 / 100	273 ms	35960 KiB

minmaxtree

#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
//ifstream cin("minmaxtree.in");
//ofstream cout("minmaxtree.out");
int t[70005],euclid[200005],niv[200005],cnt,put[20],lg[300005],rmq[20][200005],fr[200005],tata[200005],tatac[200005],ap[200005],maxim[200005],minim[200005],cod[200005],viz[70005],st[70005],dr[70005];
vector<int> temp[70005],v[70005];
vector<int> graf[70005];
struct query{
    int a,b,c;
}mi[70005],ma[70005];
void dfs(int nod,int h){
    t[nod]=1;
    euclid[++cnt]=nod;
    niv[cnt]=h;
    for(auto u:temp[nod]){
        if(t[u]==1)
            continue;
        v[nod].push_back(u);
        tata[u]=nod;
        tatac[u]=nod;
        dfs(u,h+1);
        euclid[++cnt]=nod;
        niv[cnt]=h;
    }
}
void add(int a,int b){
    graf[a].push_back(b);
}
int maa(int a,int b){
    if(niv[a]>niv[b]){
        return b;
    }
    return a;
}
int lca(int st,int dr){
    int dist=dr-st+1;
    int e=lg[dist];
    return euclid[maa(rmq[e][st],rmq[e][dr-put[e]+1])];
}
int find_lca(int a,int b){
    a=fr[a];
    b=fr[b];
    if(a>b)
        swap(a,b);
    return lca(a,b);
}
bool misort(query a,query b){
    return a.c<b.c;
}
bool masort(query a,query b){
    return a.c>b.c;
}
int mai_jos(int a,int b){
    if(niv[fr[a]]>niv[fr[b]])
        return true;
    return false;
}
void update(int jos,int sus,int val,bool ok,int ind){
    int cur=jos;
    while(mai_jos(cur,sus)==true){
        cur=tata[cur];
    }
    int nex=cur;
    cur=jos;
    while(mai_jos(cur,sus)==true){
        if(cur==0 or cur==1)
            break;
        int aux=tata[cur];
        tata[cur]=nex;
        if(ap[cod[cur]]==0){
            if(ok==0)
                maxim[cod[cur]]=ind;
            else
                minim[cod[cur]]=ind;
            ap[cod[cur]]=1;
        }
        cur=aux;
    }
}
bool cup(int w){
    if(viz[w]==1)
        return 0;
    viz[w]=1;
    for(auto u:graf[w]){
        if(dr[u]==0){
            st[w]=u;
            dr[u]=w;
            return 1;
        }
    }
    for(auto u:graf[w]){
        if(cup(dr[u])==1){
            st[w]=u;
            dr[u]=w;
            return 1;
        }
    }
    return 0;
}
pair<int,int> muchie[70005];
int main()
{
    int n,a,b,k,c,c1=0,c2=0;
    char ch;
    cin>>n;
    for(int i=1;i<n;i++){
        cin>>a>>b;
        temp[a].push_back(b);
        temp[b].push_back(a);
    }
    dfs(1,1);
    for(int i=cnt;i>=1;i--){
        fr[euclid[i]]=i;
    }
    for(int i=1;i<=cnt;i++){
        rmq[0][i]=i;
    }
    put[0]=1;
    for(int i=1;i<=18;i++){
        put[i]=put[i-1]*2;
        lg[put[i]]++;
    }
    for(int i=1;i<=200000;i++){
        lg[i]+=lg[i-1];
    }
    for(int i=1;i<=18;i++){
        for(int j=1;j<=cnt;j++){
            if(j+put[i]-1>cnt)
                break;
            rmq[i][j]=maa(rmq[i-1][j],rmq[i-1][j+put[i-1]]);
        }
    }
    cin>>k;
    cin.get();
    for(int i=1;i<=k;i++){
        cin>>ch>>a>>b>>c;
        cin.get();
        if(ch=='m'){
            mi[++c1].a=a;
            mi[c1].b=b;
            mi[c1].c=c;
        }
        else{
            ma[++c2].a=a;
            ma[c2].b=b;
            ma[c2].c=c;
        }
    }
    sort(mi+1,mi+c1+1,masort);
    sort(ma+1,ma+c2+1,misort);
    for(int i=1;i<n;i++){
        maxim[i]=-1;
        minim[i]=-1;
    }
    //for(int i=1;i<=n;i++)
        //cout<<tata[i]<<" ";
    //cout<<"\n";
    int contor=0;
    for(int i=2;i<=n;i++){
        cod[i]=++contor;
        muchie[contor]=make_pair(i,tata[i]);
    }

    for(int i=1;i<=c1;i++){
        //cout<<i<<"\n";
        int lca=find_lca(mi[i].a,mi[i].b);
        //cout<<lca<<" ";
        update(mi[i].a,lca,mi[i].c,1,i);
        update(mi[i].b,lca,mi[i].c,1,i);
    }
    for(int i=1;i<=n;i++){
        ap[i]=0;
        tata[i]=tatac[i];
    }
    for(int i=1;i<=c2;i++){
        int lca=find_lca(ma[i].a,ma[i].b);
        update(ma[i].a,lca,ma[i].c,0,i+c1);
        update(ma[i].b,lca,ma[i].c,0,i+c1);
    }
    for(int i=1;i<n;i++){
        //cout<<i<<" "<<maxim[i]<<" "<<minim[i]<<"\n";
        if(maxim[i]!=-1)
            graf[i].push_back(maxim[i]);
        if(minim[i]!=-1)
            graf[i].push_back(minim[i]);
    }
    int co=0,pco;
    do{
        pco=co;
        for(int i=1;i<n;i++){
            viz[i]=0;
        }
        for(int i=1;i<n;i++){
            if(st[i]==0){
                co+=cup(i);
            }
        }
    }while(co!=pco);
    //cout<<"\n\n";
    for(int i=1;i<n;i++){
        cout<<muchie[i].first<<" "<<muchie[i].second<<" ";
        //cout
        if(st[i]!=0){
            //cout<<i<<" ";
            if(st[i]<=c1){
                cout<<mi[st[i]].c<<"\n";
            }
            else{
                cout<<ma[st[i]-c1].c<<"\n";
            }
        }
        else{
            if(maxim[i]!=-1){
                cout<<ma[maxim[i]-c1].c<<"\n";
                continue;
            }
            if(minim[i]!=-1){
                cout<<mi[minim[i]].c<<"\n";
                continue;
            }
            cout<<1<<"\n";
        }
    }

    return 0;
}

/*
4
1 2
2 3
3 4
2
m 1 3 20
m 1 4 15
*/

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