oj.uz

Submission #209864

# Submission time Handle Problem Language Result Execution time Memory
209864 2020-03-15T18:30:46 Z thebes Min-max tree (BOI18_minmaxtree) C++14
100 / 100
 379 ms 30568 KB 
#include <bits/stdc++.h>
#define DEBUG 1
using namespace std;

namespace output{
    void __(short x){cout<<x;}
    void __(unsigned x){cout<<x;}
    void __(int x){cout<<x;}
    void __(long long x){cout<<x;}
    void __(unsigned long long x){cout<<x;}
    void __(double x){cout<<x;}
    void __(long double x){cout<<x;}
    void __(char x){cout<<x;}
    void __(const char*x){cout<<x;}
    void __(const string&x){cout<<x;}
    void __(bool x){cout<<(x?"true":"false");}
    template<class S,class T>
    void __(const pair<S,T>&x){__(DEBUG?"(":""),__(x.first),__(DEBUG?", ":" "),__(x.second),__(DEBUG?")":"");}
    template<class T>
    void __(const vector<T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");}
    template<class T>
    void __(const set<T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");}
    template<class T>
    void __(const multiset<T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");}
    template<class S,class T>
    void __(const map<S,T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");}
    void pr(){cout<<"\n";}
    template<class S,class... T>
    void pr(const S&a,const T&...b){__(a);if(sizeof...(b))__(' ');pr(b...);}
}

using namespace output;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<int,char> pic;
typedef pair<double,double> pdd;
typedef pair<ld,ld> pld;
typedef vector<int> vi;
typedef vector<ll> vl;

#define pb push_back
#define fox(i,x,y) for(int i=(x);i<=(y);i++)
#define foxr(i,x,y) for(int i=(y);i>=(x);i--)

const int MN = 70005;
int N, K, i, x, y, w, ds[MN], val[MN], dep[MN], par[MN], nxt, dn[MN], deg[MN], use[MN], hmm[MN], ra[MN], rb[MN], idd[MN], lst[MN];
int fnd(int x){return ds[x]=ds[x]==x?x:fnd(ds[x]);}
vi adj[MN]; vector<pii> g[MN]; pii ed[MN];
set<pii> st; map<pii,int> id, ans;
struct qur{int x, y, w, id;}q[MN];
vector<qur> a, b; queue<int> go;

void dfs(int n,int p,int d){
    dep[n] = d; par[n] = p;
    for(auto v : adj[n]){
        if(v==p) continue;
        dfs(v, n, d+1);
    }
}

int main(){
    scanf("%d",&N);
    for(i=1;i<N;i++){
        scanf("%d%d",&x,&y);
        adj[x].pb(y);
        adj[y].pb(x);
        id[{min(x,y),max(x,y)}]=i;
        ed[i]={x,y};
    }
    scanf("%d",&K);
    for(i=1;i<=K;i++){
        char ch;
        scanf(" %c%d%d%d",&ch,&x,&y,&w);
        q[i]={x,y,w,N+i};
        if(ch=='M') a.pb({x,y,w,i});
        else b.pb({x,y,w,i});
    }
    sort(a.begin(),a.end(),[](qur i,qur j){return i.w<j.w;});
    sort(b.begin(),b.end(),[](qur i,qur j){return i.w>j.w;});
    dfs(1, 0, 1);
    for(i=1;i<=N;i++)
        ds[i] = i;
    for(auto v : a){
        x = fnd(v.x), y = fnd(v.y);
        while(x!=y){
            if(dep[x]<dep[y]) swap(x,y);
            int cur = id[{min(x,par[x]),max(x,par[x])}];
            ra[cur] = v.id;
            hmm[cur] = v.w;
            ds[x] = fnd(par[x]);
            x = fnd(x);
        }
    }
    for(i=1;i<=N;i++)
        ds[i] = i;
    for(auto v : b){
        x = fnd(v.x), y = fnd(v.y);
        while(x!=y){
            if(dep[x]<dep[y]) swap(x,y);
            int cur = id[{min(x,par[x]),max(x,par[x])}];
            rb[cur] = v.id;
            hmm[cur] = v.w;
            ds[x] = fnd(par[x]);
            x = fnd(x);
        }
    }
    for(i=1;i<N;i++){
        ans[ed[i]]=hmm[i];
    }
    for(i=1;i<N;i++){
        if(ra[i]&&rb[i]){
            g[ra[i]].pb({rb[i],i});
            g[rb[i]].pb({ra[i],i});
        }
        else if(ra[i]) dn[ra[i]] = 1, idd[ra[i]] = i, use[i] = 1;
        else if(rb[i]) dn[rb[i]] = 1, idd[rb[i]] = i, use[i] = 1;
    }
    for(i=1;i<=K;i++){
        set<int> t;
        for(auto v : g[i])
            t.insert(v.first);
        deg[i] = t.size();
        if(deg[i]==1) dn[i]=1;
    }
    for(i=1;i<=K;i++){
        if(dn[i]) go.push(i);
        else st.insert({deg[i], i});
    }
    while(go.size()||st.size()){
        if(go.empty()){
            go.push(st.begin()->second);
            st.erase(st.begin());
        }
        int cur = go.front(); go.pop();
        if(!idd[cur]){
            for(auto v : g[cur]){
                if(!use[v.second]){
                    idd[cur]=v.second;
                    use[v.second]=1;
                    break;
                }
            }
        }
        ans[ed[idd[cur]]]=q[cur].w;
        for(auto v : g[cur]){
            if(dn[v.first]==0||dn[v.first]==cur){
                if(lst[v.first]!=cur){
                    st.erase({deg[v.first],v.first});
                    deg[v.first]--;
                    if(deg[v.first]==1){
                        dn[v.first] = cur;
                        go.push(v.first);
                    }
                    else st.insert({deg[v.first],v.first});
                    lst[v.first]=cur;
                }
                if(!use[v.second]){
                    idd[v.first] = v.second;
                    use[v.second] =1;
                }
            }
        }
    }
    for(i=1;i<N;i++){
        printf("%d %d %d\n",ed[i].first,ed[i].second,ans[ed[i]]);
    }
    return 0;
}

Compilation message

minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&N);
     ~~~~~^~~~~~~~~
minmaxtree.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&x,&y);
         ~~~~~^~~~~~~~~~~~~~
minmaxtree.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&K);
     ~~~~~^~~~~~~~~
minmaxtree.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c%d%d%d",&ch,&x,&y,&w);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3704 KB Output is correct
2 Correct 6 ms 3704 KB Output is correct
3 Correct 7 ms 3704 KB Output is correct
4 Correct 6 ms 3704 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 23400 KB Output is correct
2 Correct 247 ms 21356 KB Output is correct
3 Correct 243 ms 22124 KB Output is correct
4 Correct 268 ms 23912 KB Output is correct
5 Correct 240 ms 21996 KB Output is correct
6 Correct 264 ms 21864 KB Output is correct
7 Correct 256 ms 21348 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 19604 KB Output is correct
2 Correct 199 ms 19828 KB Output is correct
3 Correct 196 ms 21084 KB Output is correct
4 Correct 199 ms 22024 KB Output is correct
5 Correct 208 ms 20156 KB Output is correct
6 Correct 224 ms 20676 KB Output is correct
7 Correct 225 ms 20084 KB Output is correct
8 Correct 228 ms 19988 KB Output is correct

Subtask #4
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3704 KB Output is correct
2 Correct 6 ms 3704 KB Output is correct
3 Correct 7 ms 3704 KB Output is correct
4 Correct 6 ms 3704 KB Output is correct
5 Correct 280 ms 23400 KB Output is correct
6 Correct 247 ms 21356 KB Output is correct
7 Correct 243 ms 22124 KB Output is correct
8 Correct 268 ms 23912 KB Output is correct
9 Correct 240 ms 21996 KB Output is correct
10 Correct 264 ms 21864 KB Output is correct
11 Correct 256 ms 21348 KB Output is correct
12 Correct 199 ms 19604 KB Output is correct
13 Correct 199 ms 19828 KB Output is correct
14 Correct 196 ms 21084 KB Output is correct
15 Correct 199 ms 22024 KB Output is correct
16 Correct 208 ms 20156 KB Output is correct
17 Correct 224 ms 20676 KB Output is correct
18 Correct 225 ms 20084 KB Output is correct
19 Correct 228 ms 19988 KB Output is correct
20 Correct 300 ms 23728 KB Output is correct
21 Correct 251 ms 24040 KB Output is correct
22 Correct 255 ms 24168 KB Output is correct
23 Correct 260 ms 24596 KB Output is correct
24 Correct 379 ms 29792 KB Output is correct
25 Correct 357 ms 30568 KB Output is correct
26 Correct 336 ms 29668 KB Output is correct
27 Correct 353 ms 29612 KB Output is correct
28 Correct 325 ms 26976 KB Output is correct
29 Correct 319 ms 27108 KB Output is correct
30 Correct 298 ms 25836 KB Output is correct
31 Correct 297 ms 25964 KB Output is correct
32 Correct 324 ms 26888 KB Output is correct
33 Correct 336 ms 25912 KB Output is correct
34 Correct 303 ms 25892 KB Output is correct
35 Correct 307 ms 25624 KB Output is correct