Submission #1016330

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016330		MohamedFaresNebili	Beads and wires (APIO14_beads)	C++14	100 / 100	73 ms	26308 KiB

beads

    #include <bits/stdc++.h>
    	
    		using namespace std;
     
    		int N;
    		int best[200005];
    		vector<pair<int, int>> adj[200005];
    		int DP[200005], cur[200005];
    		int maxW[200005][2], sum[200005];
     
    		int nDP[200005], ncur[200005];
    		int nsum[200005];
     
    		void dfs(int v, int p) {
    			maxW[v][0] = maxW[v][1] = -1e9;
    			
    			for(auto u : adj[v]) {
    				if(u.first == p) continue;
    				dfs(u.first, v); 
    				sum[u.first] = max(DP[u.first], u.second + cur[u.first]);
    				DP[v] += sum[u.first];
    				maxW[v][1] = max(maxW[v][1], u.second + DP[u.first] - sum[u.first]);
    				if(maxW[v][0] < maxW[v][1])
    					swap(maxW[v][0], maxW[v][1]);
    			}
     
    			cur[v] = maxW[v][0] + DP[v];
     
    		}
     
    		void solve(int v, int p, int preW, int preC) {
    			if(p != -1) {
    				nDP[v] = DP[p] - sum[v] + nsum[p];
    				int c = maxW[p][0];
    				if(preW + DP[v] - sum[v] == c)
    					c = maxW[p][1];
    				c = max(c, preC);
    				ncur[v] = c + nDP[v];
    				nsum[v] = max(nDP[v], preW + ncur[v]);
    				preC = preW + nDP[v] - nsum[v];
    			}
    			for(auto u : adj[v]) {
    				if(u.first == p) continue;
    				solve(u.first, v, u.second, preC);
    			}
    		}
     
    		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});
    			}
    			dfs(1, 1); solve(1, -1, 0, -1e9);
    			int res = 0;
    			for(int l = 1; l <= N; l++) 
    				res = max(res, DP[l] + nsum[l]);
    			cout << res << "\n";
    		}

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