Submission #114216

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

beads

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef pair < int, int > pii;
typedef vector < pii > vp;
typedef long long ll;

const int N = 1e5 + 500;
const ll INF = 0x3f3f3f3f;

vp v[N];
int n, root;
ll dp[N][5];

ll f(int x,int k,int lst){
    if(dp[x][k] != -1) return dp[x][k];
    ll m0 = 0, m1 = -INF , m2 = -INF ;
    for(pii A : v[x]){
        int nxt = A.X, tez = A.Y;
        if(nxt == lst) continue;
        ll op1 = f(nxt, 0, x);
        ll op2 = f(nxt, 1, x);
        ll ob = max(op1, op2 + tez);
        //printf("X : %d nxt : %d op1 : )
        m2 = max(m2 + ob, m1 + op1 + tez);
        m1 = max(m1 + ob, m0 + op1 + tez);
        m0 += ob;
    }
    //printf("X = %d %lld %lld %lld\n", x, m0, m1, m2);
    if(k == 1)
        return dp[x][k] = m1;
    return dp[x][k] = max(m0, m2);
}

int main(){
    scanf("%d", &n);
    for(int i = 1;i < n;i++){
        int x, y, z; scanf("%d%d%d", &x, &y, &z);
        v[x].PB({y, z});
        v[y].PB({x, z});
    }
    for(root = n;root <= n;root++){
        memset(dp, -1, sizeof(dp));
        printf("%lld\n", f(root, 0, root));
    }
}

Compilation message (stderr)

beads.cpp: In function 'int main()':
beads.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
beads.cpp:46:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int x, y, z; scanf("%d%d%d", &x, &y, &z);
                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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