Submission #1258826

#TimeUsernameProblemLanguageResultExecution timeMemory
1258826StefanSebezMin-max tree (BOI18_minmaxtree)C++20
0 / 100
332 ms42480 KiB
#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],out[N],tajm,par[N][lg+1],depth[N];
void DFSsetup(int u,int p=0){
    in[u]=++tajm;
    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);
    out[u]=tajm;
}
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];
}
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);
    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};
        int c=LCA(u,v);
        int x=u;for(int i=lg;i>=0;i--) if(depth[par[x][i]]>depth[c]) x=par[x][i];
        if(x!=c){
            Ubaci[x].pb({w,bit});
            Izbaci[u].pb({w,bit});
        }
        x=v;for(int i=lg;i>=0;i--) if(depth[par[x][i]]>depth[c]) x=par[x][i];
        if(x!=c){
            Ubaci[x].pb({w,bit});
            Izbaci[v].pb({w,bit});
        }
        /*ev[u].pb({v,w,bit});
        ev[v].pb({u,w,bit});*/
        mapa1[w]=I;
        /*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 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:85:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |     scanf("%i",&n);
      |     ~~~~~^~~~~~~~~
minmaxtree.cpp:87:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |         int u,v;scanf("%i%i",&u,&v);
      |                 ~~~~~^~~~~~~~~~~~~~
minmaxtree.cpp:94:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |     scanf("%i",&K);
      |     ~~~~~^~~~~~~~~
minmaxtree.cpp:97:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |         int u,v,w;scanf("%i%i%i",&u,&v,&w);
      |                   ~~~~~^~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...