Submission #13047

#	Time	Username	Problem	Language	Result	Execution time	Memory
13047		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 *dp2[3];
        for (int i=0; i<3; i++) {
            dp2[i] = new int[graph[x].size()]();
        }
        int cnt = 0;
        for (int i=0; i<graph[x].size(); i++) {
            pi t = graph[x][i];
            if(t.second == pa){
                if(i){
                    for (int j=0; j<3; j++) {
                        dp2[j][i] = dp2[j][i-1];
                    }
                }
                continue;
            }
            int classic = f(t.second,0,x,t.first);
            int pick = f(t.second,1,x,t.first);
            int free = t.first;
            dp2[0][i] = (i ? dp2[0][i-1] : 0) + max(classic,pick);
            
            if(cnt == 0) dp2[1][i] = classic + free;
            else dp2[1][i] = max(dp2[1][i-1] + max(classic,pick),dp2[0][i-1] + classic + free);
            
            if(cnt >= 2) dp2[2][i] = dp2[2][i-1] + max(classic,pick);
            if(cnt) dp2[2][i] = max(dp2[2][i],dp2[1][i-1] + classic + free);
            cnt++;
        }
        int ret = max(dp2[0][graph[x].size()-1],dp2[2][graph[x].size()-1]);
        for(int i=0; i<3; i++){
            delete[] dp2[i];
        }
        return dp[x][m] = ret;
        
    }
    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:21: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:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
beads.cpp:69: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