oj.uz

Submission #552176

# Submission time Handle Problem Language Result Execution time Memory
552176 2022-04-22T15:19:31 Z QwertyPi Beads and wires (APIO14_beads) C++14
13 / 100
 4 ms 4948 KB 
#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pb push_back

using namespace std;
typedef pair<int, int> pii;
const int N = 2e5 + 5;
vector<pii> G[N];
int dp[N][4], W[N], p[N];

void dfs(int v, int par = -1){
	for(auto [i, w] : G[v]){
		if(i == par) continue;
		W[i] = w;
		dfs(i, v);
	}
	// Case 0: do nothing
	int a0 = 0, a1 = 0;
	for(auto [i, w] : G[v]){
		if(i != par) a0 += dp[i][2], a1 += dp[i][3];
	}
	dp[v][0] = a0, dp[v][1] = a1;
	// Case 1: p[v]-v-son[v]
	vector<pii> co2, co3;
	for(auto [i, w] : G[v]){
		if(i != par) co2.pb({w + dp[i][0] - dp[i][2], i}), co3.pb({w + dp[i][1] - dp[i][2], i});
	}
	sort(co2.begin(), co2.end(), greater<>());
	sort(co3.begin(), co3.end(), greater<>());
//	for(auto i : co2) cout << i << ' '; cout << endl;
//	for(auto i : co3) cout << i << ' '; cout << endl;
	if(par != -1){
		if(co2.size()) dp[v][2] = max(dp[v][2], a0 + co2[0].fi + W[v]);
		if(co3.size()) dp[v][3] = max(dp[v][3], a0 + co3[0].fi + W[v]);
	}
	// Case 2: son1[v]-v-son2[v]
	if(co2.size() >= 2) dp[v][1] = max(dp[v][1], a0 + (co2[0].se == co3[0].se ? max(co2[0].fi + co3[1].fi, co2[1].fi + co3[0].fi) : co2[0].fi + co3[0].fi));
	dp[v][2] = max(dp[v][0], dp[v][2]);
	dp[v][1] = max(dp[v][0], dp[v][1]);
	dp[v][3] = max(dp[v][1], dp[v][3]);
	dp[v][3] = max(dp[v][2], dp[v][3]);
}

int32_t main(){
	int n;
	cin >> n;
	for(int i = 0; i < n - 1; i++){
		int u, v, we;
		cin >> u >> v >> we;
		G[u].pb({v, we});
		G[v].pb({u, we});
	}
	dfs(1);
//	for(int i = 1; i <= n; i++){
//		cout << i << ": " << dp[i][0] << ' ' << dp[i][1] << ' ' << dp[i][2] << ' ' << dp[i][3] << endl;
//	}
	int ans = 0; for(int j = 0; j < 4; j++) ans = max(ans, dp[1][j]);
	cout << ans << endl;
}

Compilation message

beads.cpp: In function 'void dfs(long long int, long long int)':
beads.cpp:14:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   14 |  for(auto [i, w] : G[v]){
      |           ^
beads.cpp:21:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   21 |  for(auto [i, w] : G[v]){
      |           ^
beads.cpp:27:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   27 |  for(auto [i, w] : G[v]){
      |           ^

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 4 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 4 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Incorrect 4 ms 4948 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 4 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Incorrect 4 ms 4948 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 4 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Incorrect 4 ms 4948 KB Output isn't correct
14 Halted 0 ms 0 KB -