oj.uz

Submission #382313

# Submission time Handle Problem Language Result Execution time Memory
382313 2021-03-27T05:04:15 Z pure_mem Beads and wires (APIO14_beads) C++14
0 / 100
 3 ms 2688 KB 
#include <iostream>
#include <vector>

#define X first
#define Y second
#define MP make_pair
#define ll long long

using namespace std;

const int N = 1e5 + 12;
const int INF = 1e9;

int n, dp[2][N], ans;
vector< pair<int, int> > g[N];

void dfs(int v, int pr){
	dp[0][v] = -INF;
	for(pair<int, int> tmp: g[v]){
		int to = tmp.X, cost = tmp.Y;
		if(to != pr){
			dfs(to, v);
			dp[1][v] += max(dp[1][to], dp[0][to] + cost);	
		}
	} 
	int sum = dp[1][v], c1 = -INF, c2 = -INF;
	for(pair<int, int> tmp: g[v]){
		int to = tmp.X, cost = tmp.Y;
		if(to != pr){
			int dt = cost;
			if(dp[1][to] < dp[0][to] + cost)
				dt = dp[1][to] - dp[0][to];
			if(c1 < dt)
				c2 = c1, c1 = dt;
			else if(c2 < dt)
				c2 = dt;
		}
	}
	if(c1 != -INF)
		dp[0][v] = sum + c1;
	if(c2 != -INF)
		dp[1][v] = max(dp[1][v], sum + c2 + c1);
	ans = max(ans, dp[1][v]);
}

int main () {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n;
	for(int i = 1, x, y, z;i < n;i++){
		cin >> x >> y >> z;
		g[x].push_back(MP(y, z));
		g[y].push_back(MP(x, z));
	}
	dfs(1, 1);
	//cerr << dp[0][6] << "\n";
	cout << ans;
}

Subtask #1
0 / 13.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 43.0

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