Submission #1258852

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258852		StefanSebez	Min-max tree (BOI18_minmaxtree)	C++20	29 / 100	330 ms	40916 KiB

minmaxtree

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=70050,inf=1e9+50,lg=15;
int n,K;
vector<int>E[N];
map<pair<int,int>,int>mapa;
map<int,int>mapa1;
pair<int,int>grana[N];
array<int,4>Qs[N];
int lo[N],lind[N],up[N],rind[N];

/*int Par[N];
void DFS1(int u,int p=0){
    Par[u]=p;
    for(auto i:E[u]){if(i!=p) DFS1(i,u);}
}*/

int in[N],cvor[N],out[N],sajz[N],tajm,par[N][lg+1],depth[N];
void DFSsetup(int u,int p=0){
    sajz[u]=1;
    depth[u]=depth[p]+1;
    par[u][0]=p;
    for(int i=1;i<=lg;i++) par[u][i]=par[par[u][i-1]][i-1];
    for(auto i:E[u]) if(i!=p) DFSsetup(i,u),sajz[u]+=sajz[i];
}
int LCA(int u,int v){
    if(depth[u]<depth[v]) swap(u,v);
    for(int i=lg;i>=0;i--) if(depth[par[u][i]]>=depth[v]) u=par[u][i];if(u==v)return u;
    for(int i=lg;i>=0;i--) if(par[u][i]!=par[v][i]) u=par[u][i],v=par[v][i];return par[u][0];
}

int head[N];
void HLD(int u,int p=0){
    in[u]=++tajm;cvor[tajm]=u;
    if(!head[u]) head[u]=u;
    for(auto &i:E[u]) if(i==p){swap(i,E[u].back());break;}
    if(E[u][0]!=p){
        int ind=0;
        for(int i=0;i+1<E[u].size();i++) if(sajz[E[u][ind]]<sajz[E[u][i]]) ind=i;
        swap(E[u][ind],E[u][0]);
        head[E[u][0]]=head[u];
    }
    for(auto i:E[u]) if(i!=p) HLD(i,u);
    out[u]=tajm;
}

//bool Podstablo(int u,int v){if(in[u]<=in[v]&&in[v]<=out[u])return true;return false;}
//vector<array<int,3>>ev[N];
vector<pair<int,int>>Ubaci[N],Izbaci[N];
multiset<int>st[2];
/*void DFS(int u,int p=0){
    for(auto [w,bit]:Ubaci[u]) st[bit].insert(w);
    if(st[0].size()) lo[mapa[{u,p}]]=*st[0].rbegin();
    if(st[1].size()) up[mapa[{u,p}]]=*st[1].begin();
    for(auto [w,bit]:Izbaci[u]) st[bit].erase(st[bit].find(w));
    for(auto i:E[u]) if(i!=p) DFS(i,u);
    for(auto [w,bit]:Izbaci[u]) st[bit].insert(w);
    for(auto [w,bit]:Ubaci[u]) st[bit].erase(st[bit].find(w));

    for(auto [v,w,bit]:ev[u]){
        if(!Podstablo(u,v)) st[bit].erase(w);
    }
    for(int I=0,j=0;I<E[u].size();I++){
        int v=E[u][I];if(v==p) continue;
        for(int i=((int)ev[v].size())-1;i>=0;i--){
            int V=ev[v][i][0],w=ev[v][i][1],bit=ev[v][i][2];
            st[bit].insert(w);
            if(Podstablo(v,V)) break;
        }
        while(j<ev[u].size()){
            int V=ev[u][j][0],w=ev[u][j][1],bit=ev[u][j][2];
            if(!Podstablo(v,V)) break;
            st[bit].insert(w);
            j++;
        }
        DFS(v,u);
    }
    for(auto [v,w,bit]:ev[u]){
        if(st[bit].find(w)!=st[bit].end()) st[bit].erase(w);
    }
}*/
vector<int>E1[N];
int pr[N];
bool was[N];
bool Matching(int u){
    was[u]=true;
    for(auto i:E1[u]){
        if(!was[pr[i]]&&(!pr[i]||Matching(pr[i]))){
            pr[i]=u;
            return true;
        }
    }
    return false;
}
int main(){
    scanf("%i",&n);
    for(int i=1;i<n;i++){
        int u,v;scanf("%i%i",&u,&v);
        E[u].pb(v),E[v].pb(u);
        mapa[{u,v}]=mapa[{v,u}]=i;
        grana[i]={u,v};
    }
    DFSsetup(1);
    HLD(1);
    /*for(int i=1;i<=n;i++){
        printf("%i: %i %i %i\n",i,head[i],par[i][0],in[i]);
    }*/
    for(int i=1;i<=n;i++) up[i]=inf,lo[i]=-inf;
    scanf("%i",&K);
    for(int I=1;I<=K;I++){
        char type;cin>>type;
        int u,v,w;scanf("%i%i%i",&u,&v,&w);
        int bit=0;if(type=='M') bit=1;
        Qs[I]={u,v,w,bit};
        mapa1[w]=I;
        int c=LCA(u,v);
        int U=u;for(int i=lg;i>=0;i--) if(depth[par[U][i]]>depth[c]) U=par[U][i];
        if(U!=c){
            while(depth[head[u]]>=depth[U]){
                Ubaci[in[head[u]]].pb({w,bit});
                Izbaci[in[u]].pb({w,bit});
                u=par[head[u]][0];
            }
            if(head[u]==head[U]){
                Ubaci[in[U]].pb({w,bit});
                Izbaci[in[u]].pb({w,bit});
            }
        }
        int V=v;for(int i=lg;i>=0;i--) if(depth[par[V][i]]>depth[c]) V=par[V][i];
        if(V!=c){
            while(depth[head[v]]>=depth[V]){
                Ubaci[in[head[v]]].pb({w,bit});
                Izbaci[in[v]].pb({w,bit});
                v=par[head[v]][0];
            }
            if(head[v]==head[V]){
                Ubaci[in[V]].pb({w,bit});
                Izbaci[in[v]].pb({w,bit});
            }
        }
        /*ev[u].pb({v,w,bit});
        ev[v].pb({u,w,bit});*/
        /*DFS1(u);
        vector<int>vtx;
        while(v!=0) vtx.pb(v),v=Par[v];
        for(int i=0;i+1<vtx.size();i++){
            int j=mapa[{vtx[i],vtx[i+1]}];
            if(type=='M'){
                if(up[j]>w){
                    up[j]=w;
                    rind[j]=I;
                }
            }
            else{
                if(lo[j]<w){
                    lo[j]=w;
                    lind[j]=I;
                }
            }
        }*/
    }
    for(int u=1;u<=n;u++){
        for(auto [w,bit]:Ubaci[u]) st[bit].insert(w);
        if(st[0].size()) lo[mapa[{cvor[u],par[cvor[u]][0]}]]=*st[0].rbegin();
        if(st[1].size()) up[mapa[{cvor[u],par[cvor[u]][0]}]]=*st[1].begin();
        for(auto [w,bit]:Izbaci[u]) st[bit].erase(st[bit].find(w));
    }
    /*for(int i=1;i<=n;i++){
        printf("%i:\n",i);
        for(auto [w,bit]:Ubaci[i]) printf(" %i %i\n",w,bit);
        for(auto [w,bit]:Izbaci[i]) printf("  %i %i\n",w,bit);
    }*/
    /*for(int u=1;u<=n;u++){
        sort(ev[u].begin(),ev[u].end(),[&](array<int,3>a,array<int,3>b){
             int i=a[0],j=b[0];
             if(Podstablo(u,i)&&!Podstablo(u,j)) return true;
             if(!Podstablo(u,i)&&Podstablo(u,j)) return false;
             return in[i]<in[j];
        });
    }*/
    //DFS(1);
    for(int i=1;i<n;i++){
        lind[i]=mapa1[lo[i]];
        rind[i]=mapa1[up[i]];
    }
    /*for(int i=1;i<n;i++){
        printf("%i: %i %i %i %i\n",i,lo[i],lind[i],up[i],rind[i]);
    }*/
    for(int i=1;i<n;i++){
        if(lind[i]) E1[i].pb(lind[i]);
        if(rind[i]) E1[i].pb(rind[i]);
    }
    for(int i=1;i<n;i++){
        for(int j=1;j<n;j++) was[j]=false;
        Matching(i);
    }
    int res[n+10]={0};
    for(int i=1;i<=K;i++){
        int j=pr[i];
        res[j]=Qs[i][2];
    }
    for(int i=1;i<n;i++){
        printf("%i %i %i\n",grana[i].fi,grana[i].se,res[i]);
    }
    return 0;
}

Compilation message (stderr)

minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:101:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |     scanf("%i",&n);
      |     ~~~~~^~~~~~~~~
minmaxtree.cpp:103:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |         int u,v;scanf("%i%i",&u,&v);
      |                 ~~~~~^~~~~~~~~~~~~~
minmaxtree.cpp:114:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |     scanf("%i",&K);
      |     ~~~~~^~~~~~~~~
minmaxtree.cpp:117:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |         int u,v,w;scanf("%i%i%i",&u,&v,&w);
      |                   ~~~~~^~~~~~~~~~~~~~~~~~~

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