Submission #345398

#	Time	Username	Problem	Language	Result	Execution time	Memory
345398		alireza_kaviani	Beads and wires (APIO14_beads)	C++17	28 / 100	1060 ms	5612 KiB

beads

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define all(x)                      (x).begin(),(x).end()
#define Sort(x)                     sort(all((x)))
#define X                           first
#define Y                           second
#define sep                         ' '
#define endl                        '\n'
#define SZ(x)                       ll(x.size())

ll poww(ll a, ll b, ll md) {
    return (!b ? 1 : (b & 1 ? a * poww(a * a % md, b / 2, md) % md : poww(a * a % md, b / 2, md) % md));
}

const ll MAXN = 2e5 + 10;
const ll LOG = 22;
const ll INF = 8e18;
const ll MOD = 2e9 + 7; // 998244353; // 1e9 + 9;

int n , ans , dpDown[MAXN][2];
vector<pii> adj[MAXN];

void DFS(int v , int p = -1){
	dpDown[v][0] = dpDown[v][1] = 0;
	int mx = -MOD;
	for(pii i : adj[v]){
		int u = i.X , w = i.Y;
		if(u == p)	continue;
		DFS(u , v);
		dpDown[v][0] += max(dpDown[u][0] , dpDown[u][1] + w);
		dpDown[v][1] += max(dpDown[u][0] , dpDown[u][1] + w);
		mx = max(mx , dpDown[u][0] + w - max(dpDown[u][0] , dpDown[u][1] + w));
	}
	dpDown[v][1] += mx;
}

int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

	cin >> n;
	if(n > 10000)	return 0;
	for(int i = 1 ; i < n ; i++){
		int v , u , w;
		cin >> v >> u >> w;
		adj[v].push_back({u , w});
		adj[u].push_back({v , w});
	}
	for(int i = 1 ; i <= n ; i++){
		DFS(i);
		ans = max(ans , dpDown[i][0]);
	}
	cout << ans << endl;

    return 0;
}
/*

*/

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