oj.uz

Submission #209835

# Submission time Handle Problem Language Result Execution time Memory
209835 2020-03-15T16:45:11 Z thebes Min-max tree (BOI18_minmaxtree) C++14
58 / 100
 379 ms 34792 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[2*MN], deg[MN], hmm[MN];
int fnd(int x){return ds[x]=ds[x]==x?x:fnd(ds[x]);}
vi adj[MN], g[2*MN]; pii ed[MN];
set<pii> st, go; map<pii,int> id, ans;
struct qur{int x, y, w, id;}q[MN];
vector<qur> a, b;

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,N+i});
        else b.pb({x,y,w,N+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])}];
            g[v.id].pb(cur);
            g[cur].pb(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])}];
            g[v.id].pb(cur);
            g[cur].pb(v.id);
            hmm[cur] = v.w;
            ds[x] = fnd(par[x]);
            x = fnd(x);
        }
    }
    for(i=1;i<=K;i++)
        deg[N+i]=g[N+i].size();
    for(i=1;i<N;i++){
        int res = 1<<30, ot = g[i].size();
        for(auto v : g[i])
            res = min(res, deg[v]);
        if(ot==1) go.insert({res, i});
        else if(ot==2) st.insert({res, i});
        val[i] = res;
    }
    for(i=1;i<N;i++) ans[ed[i]]=hmm[i];
    while(st.size()||go.size()){
        int cur;
        if(go.size()){
            cur = go.begin()->second;
            go.erase(go.begin());
        }
        else{
            cur = st.begin()->second;
            st.erase(st.begin());
        }
        int ot = 0, hm = 1<<30;
        dn[cur] = 1;
        for(auto v : g[cur]){
            if(!dn[v]&&deg[v]<hm){
                ot = v;
                hm = deg[v];
            }
        }
        if(!ot){
            ans[ed[cur]]=hmm[cur];
            continue;
        }
        for(auto v : g[cur]){
            deg[v]--;
        }
        ans[ed[cur]]=q[ot-N].w;
        dn[ot]=1;
        cur = ot;
        for(auto v : g[cur]){
            if(dn[v]) continue;
            int res = 1<<30, cnt = 0;
            for(auto u : g[v]){
                if(!dn[u]) res=min(res,deg[u]), cnt++;
            }
            if(cnt==1){
                st.erase({val[v], v});
                val[v] = res;
                go.insert({val[v], v});
            }
            else{
                go.erase({val[v], v});
            }
        }
    }
    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 7 ms 5244 KB Output is correct
2 Correct 8 ms 5240 KB Output is correct
3 Correct 8 ms 5368 KB Output is correct
4 Correct 8 ms 5368 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 350 ms 31848 KB Output is correct
2 Correct 329 ms 31848 KB Output is correct
3 Correct 328 ms 32104 KB Output is correct
4 Correct 343 ms 34792 KB Output is correct
5 Correct 323 ms 32212 KB Output is correct
6 Correct 334 ms 32740 KB Output is correct
7 Correct 334 ms 31972 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 25108 KB Output is correct
2 Correct 255 ms 26608 KB Output is correct
3 Correct 243 ms 26976 KB Output is correct
4 Correct 248 ms 27912 KB Output is correct
5 Correct 269 ms 27452 KB Output is correct
6 Correct 280 ms 28224 KB Output is correct
7 Correct 285 ms 27636 KB Output is correct
8 Correct 280 ms 27412 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5244 KB Output is correct
2 Correct 8 ms 5240 KB Output is correct
3 Correct 8 ms 5368 KB Output is correct
4 Correct 8 ms 5368 KB Output is correct
5 Correct 350 ms 31848 KB Output is correct
6 Correct 329 ms 31848 KB Output is correct
7 Correct 328 ms 32104 KB Output is correct
8 Correct 343 ms 34792 KB Output is correct
9 Correct 323 ms 32212 KB Output is correct
10 Correct 334 ms 32740 KB Output is correct
11 Correct 334 ms 31972 KB Output is correct
12 Correct 253 ms 25108 KB Output is correct
13 Correct 255 ms 26608 KB Output is correct
14 Correct 243 ms 26976 KB Output is correct
15 Correct 248 ms 27912 KB Output is correct
16 Correct 269 ms 27452 KB Output is correct
17 Correct 280 ms 28224 KB Output is correct
18 Correct 285 ms 27636 KB Output is correct
19 Correct 280 ms 27412 KB Output is correct
20 Incorrect 379 ms 32180 KB Output isn't correct
21 Halted 0 ms 0 KB -