Submission #248914

#	Time	Username	Problem	Language	Result	Execution time	Memory
248914		patrikpavic2	Beads and wires (APIO14_beads)	C++17	0 / 100	26 ms	45056 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 = 6e5 + 500;
const ll INF = 1e15;
 
vector < int > g[N];
ll zbr[N], dp[3][N];
vector < pair < ll, int > > kand[N];
int n, jesam[N], vr[N], v[N]; 
 
ll f(int x, int fl, int brd){
	if(dp[fl][brd] != -1) 
		return dp[fl][brd];
	int lst = v[brd ^ 1];
	//printf("pozvao x = %d fl = %d lst = %d\n", x, fl, lst);
	//printf("brd = %d jesam = %d\n", brd, jesam[x]);
	if(brd > 2 * n)
		lst = v[brd];
	if(jesam[x] == -1){
		ll sm = 0;
		for(int nxt : g[x]){
			if(v[nxt] == lst) continue;
			ll opt = max(f(v[nxt], 0, nxt), f(v[nxt], 1, nxt) + (ll)vr[nxt]);
			sm += opt;
			kand[x].PB({f(v[nxt], 2, nxt) + vr[nxt] - opt, v[nxt]});
		}
		kand[x].PB({-INF, -1}); 
		kand[x].PB({-INF, -1}); 
		//printf("									pripream teren s x = %d\n", x);
		sort(kand[x].rbegin(), kand[x].rend());
		jesam[x] = (x == lst ? -2 : brd ^ 1); zbr[x] = sm;
		return dp[fl][brd] = sm + kand[x][0].X * (fl == 1);
	}
	if(jesam[x] >= 0 && v[jesam[x]] == lst){
		return dp[fl][brd] = zbr[x] + kand[x][0].X * (fl == 1);		
	}
	if(jesam[x] != -2){
		ll opt = max(f(v[jesam[x]], 0, jesam[x]), f(v[jesam[x]], 1, jesam[x]) + vr[jesam[x]]);
		zbr[x] += opt;
		//printf("													ovdje je x = %d\n", x);
		kand[x].PB({f(v[jesam[x]], 2, jesam[x]) + vr[jesam[x]] - opt, v[jesam[x]]});
		sort(kand[x].rbegin(), kand[x].rend());
		jesam[x] = -2;
	}
	ll sm = zbr[x] - (x == lst ? 0 : max(f(lst, 0, brd ^ 1), f(lst, 1, brd ^ 1) + vr[brd]));
	//printf("			tu sam dosao %d\n", (int)kand[1].size());
	ll dod = kand[x][0].X;
	if(kand[x][0].Y == lst)
		dod = kand[x][1].X;
	//printf("zavrsio x = %d fl = %d lst = %d --> %lld + %lld\n", x, fl, lst, sm , dod * (fl == 1));
	return dp[fl][x] = sm + dod * (fl == 1);		
}
 
 
int main(){
	memset(dp, -1, sizeof(dp));
	memset(jesam , -1, sizeof(jesam));
	scanf("%d", &n);
	for(int i = 0;i + 1 < n;i++){
		int x, y, z; scanf("%d%d%d", &x, &y, &z);
		g[x].PB(2 * i), g[y].PB(2 * i + 1);
		v[2 * i] = y, v[2 * i + 1] = x;
		vr[2 * i] = z, vr[2 * i + 1] = z;
	}
	for(int i = 1;i <= n;i++)
		v[2 * n + i] = i;
	ll sol = 0;
	for(int i = 1;i <= n;i++)
		sol = max(sol, f(i, 0, 2 * n + i));
	printf("%lld\n", sol);
	return 0;
}

Compilation message (stderr)

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