Submission #1015713

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015713		MohamedFaresNebili	Beads and wires (APIO14_beads)	C++14	28 / 100	1042 ms	7004 KiB

beads

#include <bits/stdc++.h>
	
		using namespace std;

		int N;
		vector<pair<int, int>> adj[200005];
		int DP[200005], cur[200005];

		void dfs(int v, int p) {
			int maxW = -1e9;
			
			for(auto u : adj[v]) {
				if(u.first == p) continue;
				dfs(u.first, v); 
				int sum = max(DP[u.first], u.second + cur[u.first]);
				DP[v] += sum;
				maxW = max(maxW, u.second + DP[u.first] - sum);
			}

			cur[v] = maxW + DP[v];

		}

		int32_t main() {
			ios_base::sync_with_stdio(0);
			cin.tie(0); cout.tie(0);

			cin >> N;
			for(int l = 0; l < N - 1; l++) {
				int U, V, W; cin >> U >> V >> W;
				adj[U].push_back({V, W});
				adj[V].push_back({U, W});
			}
			int res = 0;
			for(int l = 1; l <= N; l++) {
				for(int i = 1; i <= N; i++)
					DP[i] = cur[i] = 0;
				dfs(l, l); res = max(res, DP[l]);
			}
			cout << res << "\n";
		}

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