Submission #13054

#	Time	Username	Problem	Language	Result	Execution time	Memory
13054		gs14004	Beads and wires (APIO14_beads)	C++14	0 / 100	7 ms	6528 KiB

beads

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <utility>
#include <vector>
using namespace std;
typedef pair<int,int> pi;

vector<pi> graph[200005];
int n;
int dp[200005][2];

int f(int x, int m, int pa, int e){
    if(~dp[x][m]) return dp[x][m];
    if(m == 0){
        int r = 0;
        vector<int> addi;
        for (int i=0; i<graph[x].size(); i++) {
            pi t = graph[x][i];
            if(t.second == pa) continue;
            int classic = f(t.second,0,x,t.first);
            int pick = f(t.second,1,x,t.first);
            int free = t.first;
            r += max(classic,pick);
            addi.push_back(classic + free - max(classic,pick));
        }
        int r2 = 0;
        if(addi.size() >= 2){
            auto x = max_element(addi.begin(),addi.end());
            r2 += *x;
            *x = -1;
            x = max_element(addi.begin(),addi.end());
            r2 += *x;
        }
        return dp[x][m] = r + max(r2,0);
    }
    else{
        int ret = 0;
        int addi = 0;
        for(pi i : graph[x]){
            if(i.second == pa) continue;
            int classic = max(f(i.second,0,x,i.first),f(i.second,1,x,i.first));
            int pick = f(i.second,0,x,i.first) + i.first + e;
            ret += classic;
            addi = max(addi,pick - classic);
        }
        return dp[x][m] = ret + addi;
    }
}

int main(){
    memset(dp,-1,sizeof(dp));
    scanf("%d",&n);
    for (int i=0; i<n-1; i++) {
        int s,e,x;
        scanf("%d %d %d",&s,&e,&x);
        graph[s].push_back(pi(x,e));
        graph[e].push_back(pi(x,s));
    }
    printf("%d",f(1,0,0,0));
}

Compilation message (stderr)

beads.cpp: In function 'int f(int, int, int, int)':
beads.cpp:18:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i=0; i<graph[x].size(); i++) {
                       ~^~~~~~~~~~~~~~~~
beads.cpp: In function 'int main()':
beads.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
beads.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d",&s,&e,&x);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~

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