oj.uz

Submission #14702

# Submission time Handle Problem Language Result Execution time Memory
14702 2015-06-11T07:37:44 Z Namnamseo Beads and wires (APIO14_beads) C++
0 / 100
 9 ms 9728 KB 
#include <cstdio>
#include <algorithm>
#include <vector>
#define t first
#define c second
using namespace std;
typedef pair<int,int> pp;
vector<pp> e[200010];
vector<int> child[200010];
int pr[200010];
int n;
typedef long long ll;
ll memo[200010][2];
bool exist[200010][2];
void fd(int pos){
    int i,s,n;
    for(s=e[pos].size(),i=0;i<s;++i){
        n=e[pos][i].t;
        if(pr[pos]!=n){
            pr[n]=pos;
            child[pos].push_back(n);
            fd(n);
        }
    }
}
pair<ll,ll> top2(pair<ll,ll> a,ll b){
    if(a.second>b) return a;
    else {
        if(b>a.first) return {b,a.first};
        else return {a.first,b};
    }
}
ll dfs(int pos,bool can){
    if(exist[pos][can]) return memo[pos][can];
    // case 1 : tada
    int i,s,n;
    ll ret=0;
    ll ans=0;
    for(s=child[pos].size(),i=0;i<s;++i){
        n=child[pos][i];
        if(pr[pos]!=n) ans+=dfs(n,true);
    }
    ret=ans; 
    if(can){
        // case 2 : pin this
        pair<ll,ll> maxer = {-(1LL<<60),-(1LL<<60)};
        ll cs=0;
        for(s=e[pos].size(),i=0;i<s;++i){
            n=e[pos][i].t;
            if(pr[pos]!=n){
                cs+=dfs(n,true);
                maxer=top2(maxer,e[pos][i].c+dfs(n,false)-dfs(n,true));
            }
        }
        if(maxer.second>-(1LL<<60)) ret=max(ret,cs+maxer.first+maxer.second);
        // case 3 : stretch
        int j,ss,nn;
        for(s=e[pos].size(),i=0;i<s;++i){
            n=e[pos][i].t;
            if(pr[pos]!=n){
                for(ss=e[n].size(),j=0;j<ss;++j){
                    nn=e[n][j].t;
                    if(pr[n]!=nn){
                        ret=max(ret,ans+e[pos][i].c+e[n][j].c+dfs(n,false)-dfs(n,true)+dfs(nn,false)-dfs(nn,true));
                    }
                }
            }
        }
    }
    exist[pos][can]=true;
    return memo[pos][can]=ret;
}
int main()
{
    scanf("%d",&n);
    int i,a,b,c;
    for(i=1;i<n;++i) scanf("%d%d%d",&a,&b,&c), e[a].push_back({b,c}), e[b].push_back({a,c});
    fd(1);
    printf("%lld\n",dfs(1,true));
    return 0;
}

Compilation message

beads.cpp: In function 'int main()':
beads.cpp:75:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
beads.cpp:77:69: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1;i<n;++i) scanf("%d%d%d",&a,&b,&c), e[a].push_back({b,c}), e[b].push_back({a,c});
                      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9728 KB Output is correct
2 Incorrect 9 ms 9728 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9728 KB Output is correct
2 Incorrect 9 ms 9728 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9728 KB Output is correct
2 Incorrect 9 ms 9728 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9728 KB Output is correct
2 Incorrect 9 ms 9728 KB Output isn't correct
3 Halted 0 ms 0 KB -