oj.uz

Submission #347097

# Submission time Handle Problem Language Result Execution time Memory
347097 2021-01-11T18:03:15 Z negar_a Beads and wires (APIO14_beads) C++14
0 / 100
 4 ms 5100 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define mp make_pair
#define pii pair <int, int>
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define F first
#define S second

const int maxn = 2e5 + 10;
vector <pii> adj[maxn];
ll dp[5][maxn];
int inf = 1e9;
//dp[0][u] = max gain age u too hish gilasi vasat nabashe!
//dp[1][u] = max gain age u bein pedar o yeki az bache hash bashe
//dp[2][u] = max gain age u bein do ta az bache hash bashe 
//ans = max(dp[0 , 2][0]) !

void dfs(int u, int p = -1){
	int mx1 = -inf, mx2 = -inf;
	for(auto i : adj[u]){
		int v = i.F;
		if(v != p){
			dfs(v, u);
			if(dp[1][v])
				dp[1][v] += i.S;
				
			dp[0][u] += dp[1][v];
			
			int x = max(dp[0][v], dp[2][v]);
			x += i.S;
				 
			if(mx1 < (x - dp[1][v])){
				mx2 = mx1;
				mx1 = (x - dp[1][v]);
			}else if(mx2 < (x - dp[1][v])){
				mx2 = (x - dp[1][v]);
			}
		}
	}
	dp[1][u] = dp[2][u] = dp[0][u];
	dp[1][u] = (adj[u].size() > 1 || u == 0) ? dp[1][u] + mx1 : 0;
	dp[2][u] += (((int)adj[u].size() > 2) || (u == 0 && (int)adj[u].size() > 1)) ? mx2 + mx1 : 0;
//	cout << u + 1 << " " << dp[0][u] << " " << dp[1][u] << " " << dp[2][u] << " | " << mx1 << " " << mx2 << " !!! " << endl;
}

int main(){
	fast_io;
	int n;
	cin >> n;
	for(int i = 0; i < n - 1; i ++){
		int a, b, c;
		cin >> a >> b >> c;
		a --; b --;
		adj[a].pb({b, c});
		adj[b].pb({a, c});	
	}
	dfs(0);
	cout << max({dp[0][0], dp[2][0]});
	
	return 0;
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 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 4 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 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 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 4 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 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 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 4 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 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 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 4 ms 5100 KB Output isn't correct
7 Halted 0 ms 0 KB -