oj.uz

Submission #235682

# Submission time Handle Problem Language Result Execution time Memory
235682 2020-05-29T11:01:28 Z oolimry Beads and wires (APIO14_beads) C++14
0 / 100
 7 ms 4992 KB 
#include <bits/stdc++.h>
#define norope first
#define v first
#define rope second
#define w second
#define all(x) x.begin(), x.end()
using namespace std;
typedef pair<long long, long long> ii;
const long long inf = 1023456789012345;
vector<ii> adj[200005];

///norope, red edge to parent is normal
///rope, blue edge to parent is normal
///norope, blue edge to parent is normal
///each node can only have <= 2 special edges from children.
///if 1 special, then node is rope. if 0 or 2, then is norope

ii dfs(int u, int p){
	vector<long long> specialDifference = {-inf, -inf};
	long long sumNormal = 0;
	
	for(ii e : adj[u]){
		if(e.v == p) continue;
		ii res = dfs(e.v, u);
		
		long long normal = max(e.w + res.rope, res.norope);
		long long special = e.w + res.norope;
				
		sumNormal += normal;
		specialDifference.push_back(special - normal);
	}
	
	sort(all(specialDifference), greater<long long>());
	
	ii ans;
	ans.norope = max(sumNormal + specialDifference[0] + specialDifference[1], sumNormal);
	ans.rope = sumNormal + specialDifference[0];
	
	return ans;
}

int main(){
	ios_base::sync_with_stdio(false);
	
	int n; cin >> n;
	for(int i = 1;i < n;i++){
		int u, v, w; cin >> u >> v >> w;
		adj[u].push_back(ii(v,w));
		adj[v].push_back(ii(u,w));
	}
	
	cout << dfs(1,0).norope;
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB Output is correct
2 Correct 7 ms 4992 KB Output is correct
3 Correct 7 ms 4992 KB Output is correct
4 Correct 7 ms 4992 KB Output is correct
5 Correct 7 ms 4992 KB Output is correct
6 Incorrect 7 ms 4992 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB Output is correct
2 Correct 7 ms 4992 KB Output is correct
3 Correct 7 ms 4992 KB Output is correct
4 Correct 7 ms 4992 KB Output is correct
5 Correct 7 ms 4992 KB Output is correct
6 Incorrect 7 ms 4992 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB Output is correct
2 Correct 7 ms 4992 KB Output is correct
3 Correct 7 ms 4992 KB Output is correct
4 Correct 7 ms 4992 KB Output is correct
5 Correct 7 ms 4992 KB Output is correct
6 Incorrect 7 ms 4992 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB Output is correct
2 Correct 7 ms 4992 KB Output is correct
3 Correct 7 ms 4992 KB Output is correct
4 Correct 7 ms 4992 KB Output is correct
5 Correct 7 ms 4992 KB Output is correct
6 Incorrect 7 ms 4992 KB Output isn't correct
7 Halted 0 ms 0 KB -