Submission #135090

#	Time	Username	Problem	Language	Result	Execution time	Memory
135090		arthur_nascimento	Beads and wires (APIO14_beads)	C++14	100 / 100	429 ms	30516 KiB

beads

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define maxn 201000
#define debug 

#define pii pair<int,int>

vector<pii> L[maxn];

int dp[2][2][maxn];

int get(int hat,int need,int vx,int p=-1){

  //  fprintf(stderr,"%d %d %d\n",need,vx,p);
     int &r = dp[hat][need][vx];
    if(r+1) return r;
    
    int st=0;
    vector<int> vs;

    int fi = L[vx].size();
    if(vx)fi--;
    
    r = 0;
    int l = L[vx].size();
    if(need == 0){
        
        if(hat && fi >= 2) {
            
            int stot= 0;
            vector<int> ss;
            
            int bestj=-1e7, whoj, best2=-1e7;
            
            for(int k=0;k<l;k++){
                    int to = L[vx][k].first;  //  fprintf(stderr,"to %d\n",to);
                    int val = max(get(0,0,to,vx), get(0,1,to,vx) + L[vx][k].second);
                    if(to != p)stot += val,
                                 ss.pb(val);
                    else {ss.pb(0);continue;}
                    
                    int up = L[vx][k].second + get(1,0,to,vx);
                    up = up-val;
                    if(vx ==5) 
                    debug("!!!to %d novo %d ant %d\n",to,L[vx][k].second + get(1,0,to,vx),val);
                    if(up > bestj){
                        best2 = bestj;
                        bestj= up;
                        whoj = k;
                    }
                    else if(up > best2) best2 = up;
            }
            
            for(int i=0;i<l;i++){//for(int j=i+1;j<l;j++){
                int A = L[vx][i].first;//, B = L[vx][j].first;
                if(A == p) continue;
                
                int s = L[vx][i].second + get(0,0,A,vx);
                int add = bestj;
                if(whoj == i) add = best2;
               
                s += stot - ss[i] + add;
                r = max(r,s);
                if(s == 39 && vx == 5) debug("! i %d(%d) whoj %d-- 2nd %d\n",i,A,whoj, best2);
            }
        }
        
        st=0;
        vs.clear();
        for(int k=0;k<l;k++){
                    int to = L[vx][k].first;
                    if(to != p) st += max(get(0,0,to,vx), get(0,1,to,vx) + L[vx][k].second),
                            vs.pb(max(get(0,0,to,vx), get(0,1,to,vx) + L[vx][k].second));
                    else vs.pb(0);
            }
        
        int no = 0;
        for(int spec=0;spec<l;spec++){
            no=0;
            int to = L[vx][spec].first;
            if(to == p) continue;
            no += max(get(hat,0,to,vx), get(hat,1,to,vx) + L[vx][spec].second);
           /* for(int k=0;k<l;k++){
                    int to = L[vx][k].first;
                    int hh = (hat && (spec==k));
                    if(to != p) no += max(get(hh,0,to,vx), get(hh,1,to,vx) + L[vx][k].second);
            }*/
            no += st - vs[spec];
            r = max(r,no);
        }
        r = max(r,no);
       if(vx == 5) debug("dp[%d][%d][%d]=%d\n",hat,need,vx,r);
        return r;
    }
    
    if(L[vx].size()==1){ 
        r = -1e7;
        return r;
    }
    
     st = 0;
    vs.clear();
    for(int j=0;j<L[vx].size();j++){
            int to = L[vx][j].first;
            if(to == p ) vs.pb(0);
            else
                 st += max(get(0,0,to,vx), get(0,1,to,vx) + L[vx][j].second),
                 vs.pb(max(get(0,0,to,vx), get(0,1,to,vx) + L[vx][j].second));
        }
    
    for(int i=0;i<L[vx].size();i++){
        int s = 0;
        if(L[vx][i].first == p) continue;
        s = L[vx][i].second + get(hat,0,L[vx][i].first,vx);
        s += st - vs[i];
        r = max(r,s);
    }
    if(vx == 5) debug("dp[%d][%d][%d]=%d\n",hat,need,vx,r);
    return r;
    
}

int main() {
    int n;
    scanf("%d",&n);
    for(int i=0;i<n-1;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c), a--, b--;
        L[a].pb(pii(b,c));
        L[b].pb(pii(a,c));
    }
    memset(dp,-1,sizeof(dp));
    printf("%d\n",get(1,0,0));
    //printf("%d\n",get(0,0,1));
}

Compilation message (stderr)

beads.cpp: In function 'int get(int, int, int, int)':
beads.cpp:46:55: warning: left operand of comma operator has no effect [-Wunused-value]
                     debug("!!!to %d novo %d ant %d\n",to,L[vx][k].second + get(1,0,to,vx),val);
                                                       ^~
beads.cpp:46:89: warning: right operand of comma operator has no effect [-Wunused-value]
                     debug("!!!to %d novo %d ant %d\n",to,L[vx][k].second + get(1,0,to,vx),val);
                                                                                         ^
beads.cpp:46:74: warning: value computed is not used [-Wunused-value]
                     debug("!!!to %d novo %d ant %d\n",to,L[vx][k].second + get(1,0,to,vx),val);
beads.cpp:65:78: warning: left operand of comma operator has no effect [-Wunused-value]
                 if(s == 39 && vx == 5) debug("! i %d(%d) whoj %d-- 2nd %d\n",i,A,whoj, best2);
                                                                              ^
beads.cpp:65:80: warning: right operand of comma operator has no effect [-Wunused-value]
                 if(s == 39 && vx == 5) debug("! i %d(%d) whoj %d-- 2nd %d\n",i,A,whoj, best2);
                                                                                ^
beads.cpp:65:82: warning: right operand of comma operator has no effect [-Wunused-value]
                 if(s == 39 && vx == 5) debug("! i %d(%d) whoj %d-- 2nd %d\n",i,A,whoj, best2);
                                                                                  ^~~~
beads.cpp:65:88: warning: right operand of comma operator has no effect [-Wunused-value]
                 if(s == 39 && vx == 5) debug("! i %d(%d) whoj %d-- 2nd %d\n",i,A,whoj, best2);
                                                                                        ^~~~~
beads.cpp:93:48: warning: left operand of comma operator has no effect [-Wunused-value]
        if(vx == 5) debug("dp[%d][%d][%d]=%d\n",hat,need,vx,r);
                                                ^~~
beads.cpp:93:52: warning: right operand of comma operator has no effect [-Wunused-value]
        if(vx == 5) debug("dp[%d][%d][%d]=%d\n",hat,need,vx,r);
                                                    ^~~~
beads.cpp:93:57: warning: right operand of comma operator has no effect [-Wunused-value]
        if(vx == 5) debug("dp[%d][%d][%d]=%d\n",hat,need,vx,r);
                                                         ^~
beads.cpp:93:60: warning: right operand of comma operator has no effect [-Wunused-value]
        if(vx == 5) debug("dp[%d][%d][%d]=%d\n",hat,need,vx,r);
                                                            ^
beads.cpp:104:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0;j<L[vx].size();j++){
                 ~^~~~~~~~~~~~~
beads.cpp:112:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<L[vx].size();i++){
                 ~^~~~~~~~~~~~~
beads.cpp:119:45: warning: left operand of comma operator has no effect [-Wunused-value]
     if(vx == 5) debug("dp[%d][%d][%d]=%d\n",hat,need,vx,r);
                                             ^~~
beads.cpp:119:49: warning: right operand of comma operator has no effect [-Wunused-value]
     if(vx == 5) debug("dp[%d][%d][%d]=%d\n",hat,need,vx,r);
                                                 ^~~~
beads.cpp:119:54: warning: right operand of comma operator has no effect [-Wunused-value]
     if(vx == 5) debug("dp[%d][%d][%d]=%d\n",hat,need,vx,r);
                                                      ^~
beads.cpp:119:57: warning: right operand of comma operator has no effect [-Wunused-value]
     if(vx == 5) debug("dp[%d][%d][%d]=%d\n",hat,need,vx,r);
                                                         ^
beads.cpp: In function 'int main()':
beads.cpp:126:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
beads.cpp:129:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d",&a,&b,&c), a--, b--;
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
beads.cpp: In function 'int get(int, int, int, int)':
beads.cpp:61:17: warning: 'whoj' may be used uninitialized in this function [-Wmaybe-uninitialized]
                 if(whoj == i) add = best2;
                 ^~

• Subtask 1: 13 / 13
• Subtask 2: 15 / 15
• Subtask 3: 29 / 29
• Subtask 4: 43 / 43