Submission #248902

#	Time	Username	Problem	Language	Result	Execution time	Memory
248902		patrikpavic2	Beads and wires (APIO14_beads)	C++17	28 / 100	1078 ms	8448 KiB

beads

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

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

using namespace std;

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

const int N = 2e5 + 500;
const ll INF = 2e13;

vector < pii > v[N];
unordered_map < ll, ll > dp[3];
int n;


ll f(int x, int fl, int lst){
	if(dp[fl][x * N + lst] != 0) 
		return dp[fl][x * N + lst] - 69420;
	ll sm = 0, dod = -INF;
	for(pii nxt : v[x]){
		if(nxt.X == lst) continue;
		ll opt = max(f(nxt.X, 0, x), f(nxt.X, 1, x) + (ll)nxt.Y);
		sm += opt;
		dod = max(dod, f(nxt.X, 2, x) + nxt.Y - opt);
	}
	dp[fl][x * N + lst] = sm + dod * (fl == 1) + 69420;
	return sm + dod * (fl == 1);		
}


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});
	}
	ll sol = 0;
	for(int i = 1;i <= n;i++)
		sol = max(sol, f(i, 0, i));
	printf("%lld\n", sol);
	return 0;
}

Compilation message (stderr)

beads.cpp: In function 'int main()':
beads.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
beads.cpp:42:21: 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: 13 / 13
• Subtask 2: 15 / 15
• Subtask 3: 0 / 29
• Subtask 4: 0 / 43