Submission #248968

#	Time	Username	Problem	Language	Result	Execution time	Memory
248968		patrikpavic2	Beads and wires (APIO14_beads)	C++17	100 / 100	392 ms	58064 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 = 4e5 + 500;
const int INF = 2e9;
 
vector < int > g[N];
int dp[2][2 * N], zbr[N];
vector < pair < int, int > > kand[N];
int n, jesam[N], u[N], v[N], vr[N];
 
 
 
int f(int x, int fl, int brd){
	if(dp[fl][2 * brd + (u[brd] == x)] != -1)
		return dp[fl][2 * brd + (u[brd] == x)];
	//char c; scanf("%c", &c);
	int lst = x;
	if(brd < n){
		lst = u[brd];
		if(u[brd] == x)
			lst = v[brd];
	}	
	//printf("x = %d fl = %d lst = %d brd = %d\n", x, fl, lst, brd);
	if(jesam[x] == -1){
		int sm = 0;
		for(int nxt : g[x]){
			int cv = (u[nxt] == x ? v[nxt] : u[nxt]);
			if(cv == lst) continue;
			int opt = max(f(cv, 0, nxt), f(cv, 1, nxt) + vr[nxt]);
			sm += opt;
			kand[x].PB({f(cv, 0, nxt) + vr[nxt] - opt, cv});
		}
		kand[x].PB({-INF, -1}); 
		sort(kand[x].rbegin(), kand[x].rend());
		jesam[x] = (x == lst ? -2 : brd); zbr[x] = sm;
		//printf("x = %d fl = %d lst = %d --> %d + %d\n", x, fl, lst, sm, kand[x][0].X);
		//printf("jesam[ %d ] = %d\n", x, jesam[x]);
		return dp[fl][2 * brd + (u[brd] == x)] = sm + kand[x][0].X * (fl == 1);
	}
	if(jesam[x] >= 0 && (u[jesam[x]] == lst || v[jesam[x]] == lst) && lst != x){
		return dp[fl][2 * brd + (u[brd] == x)] = zbr[x] + kand[x][0].X * (fl == 1);		
	}
	if(jesam[x] != -2){
		int cv = u[jesam[x]];
		if(cv == x)
			cv = v[jesam[x]];
		//printf("tu sam cv = %d\n", cv);
		int opt = max(f(cv, 0, jesam[x]), f(cv, 1, jesam[x]) + vr[jesam[x]]);
		zbr[x] += opt;
		kand[x].PB({f(cv, 0, jesam[x]) + vr[jesam[x]] - opt, cv});
		sort(kand[x].rbegin(), kand[x].rend());
		jesam[x] = -2;
	}
	int sm = zbr[x] - (x == lst ? 0 : max(f(lst, 0, brd), f(lst, 1, brd) + vr[brd]));
	int dod = kand[x][0].X;
	if(kand[x][0].Y == lst)
		dod = kand[x][1].X;
	//printf("x = %d fl = %d lst = %d --> %d + %d\n", x, fl, lst, sm , dod * (fl == 1));
	return dp[fl][2 * brd + (u[brd] == x)] = sm + dod * (fl == 1);		
}
 
 
int main(){
	memset(dp, -1, sizeof(dp));
	memset(jesam, -1, sizeof(jesam));
	scanf("%d", &n);
	for(int i = 1;i < n;i++){
		int x, y, z; scanf("%d%d%d", &x, &y, &z);
		g[x].PB(i), g[y].PB(i);
		u[i] = x, v[i] = y, vr[i] = z;
	}
	int sol = 0;
	for(int i = 1;i <= n;i++)
		sol = max(sol, f(i, 0, n + i));
	printf("%d\n", sol);
	return 0;
}

Compilation message (stderr)

beads.cpp: In function 'int main()':
beads.cpp:81:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
beads.cpp:83: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: 43 / 43