Submission #248961

#	Time	Username	Problem	Language	Result	Execution time	Memory
248961		patrikpavic2	Beads and wires (APIO14_beads)	C++17	57 / 100	453 ms	131076 KiB

beads

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
 
#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 = 2e9;
 
vector < pii > v[N];
gp_hash_table < ll, int > dp[2];
gp_hash_table < ll, int > vr;
ll zbr[N];
vector < pair < ll, int > > kand[N];
int n, jesam[N];
 
 
 
ll f(int x, int fl, int lst){
	if(dp[fl][(ll)x * N + lst] != 0) 
		return dp[fl][(ll)x * N + lst] - 1;
	//printf("x = %d fl = %d lst = %d\n", x, fl, lst);
	//char c; scanf("%c", &c);
	if(!jesam[x]){
		ll sm = 0;
		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;
			kand[x].PB({f(nxt.X, 0, x) + nxt.Y - opt, nxt.X});
		}
		kand[x].PB({-INF, -1}); 
		kand[x].PB({-INF, -1}); 
		sort(kand[x].rbegin(), kand[x].rend());
		jesam[x] = (x == lst ? n + 1 : lst); zbr[x] = sm;
		return (dp[fl][(ll)x * N + lst] = sm + kand[x][0].X * (fl == 1) + 1) - 1;
	}
	if(jesam[x] == lst){
		return (dp[fl][(ll)x * N + lst] = zbr[x] + kand[x][0].X * (fl == 1) + 1) - 1;		
	}
	if(jesam[x] < n + 1){
		ll opt = max(f(jesam[x], 0, x), f(jesam[x], 1, x) + vr[(ll)x * N + jesam[x]]);
		zbr[x] += opt;
		kand[x].PB({f(jesam[x], 0, x) + vr[(ll)x * N + jesam[x]] - opt, jesam[x]});
		sort(kand[x].rbegin(), kand[x].rend());
		jesam[x] = n + 1;
	}
	ll sm = zbr[x] - (x == lst ? 0 : max(f(lst, 0, x), f(lst, 1, x) + vr[(ll)x * N + lst]));
	ll dod = kand[x][0].X;
	if(kand[x][0].Y == lst)
		dod = kand[x][1].X;
	//printf("x = %d fl = %d lst = %d --> %lld + %lld\n", x, fl, lst, sm , dod * (fl == 1));
	return (dp[fl][(ll)x * N + lst] = sm + dod * (fl == 1) + 1) - 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});
		vr[(ll)x * N + y] = z, vr[(ll)y * N + 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:69:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
beads.cpp:71: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: 29 / 29
• Subtask 4: 0 / 43