oj.uz

Submission #342668

# Submission time Handle Problem Language Result Execution time Memory
342668 2021-01-02T15:53:45 Z minoum Beads and wires (APIO14_beads) C++17
0 / 100
 4 ms 5100 KB 
#include<bits/stdc++.h>

using namespace std;
typedef long long int ll;

#define ll int

const int MAXN = 2e5 + 10, inf = INT_MAX / 4;
int n, dp[3][MAXN], tmp[MAXN], last[MAXN], parw[MAXN], mx[MAXN];
vector <pair<int,int>> adj[MAXN];

void dfs(int v, int parv){
	tmp[v] = -inf;
	for(auto i: adj[v]){
		int u = i.first, w = i.second;
		if(u == parv) continue;
		parw[u] = w;
		dfs(u, v);
		dp[1][v] = max(dp[1][v]+ mx[u], dp[0][v]+parw[v]+w+max(dp[0][u], dp[2][u]));
		dp[2][v] = max(dp[2][v]+mx[u], tmp[v]+w+max(dp[0][u],dp[2][u]));
		tmp[v] = max(tmp[v]+mx[u], dp[0][v]+w+max(dp[0][u],dp[2][u]));
		dp[0][v] += mx[u];
	}
	mx[v] = max(max(dp[0][v], dp[1][v]), dp[2][v]);
	return;
}

int32_t main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n;
	
	for(int i = 0; i < n-1; i++){
		int a, b, w;
		cin >> a >> b >> w; a--; b--;
		adj[a].push_back({b, w});
		adj[b].push_back({a, w});
	}
	dfs(0, -1);
	cout << max(dp[0][0],dp[2][0]) << '\n';
	return 0; 
}

Subtask #1
0 / 13.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 43.0

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