Submission #14702

#	Time	Username	Problem	Language	Result	Execution time	Memory
14702		Namnamseo	Beads and wires (APIO14_beads)	C++98	0 / 100	9 ms	9728 KiB

beads

#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 (stderr)

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
• Subtask 2: 0 / 15
• Subtask 3: 0 / 29
• Subtask 4: 0 / 43