oj.uz

Submission #198223

# Submission time Handle Problem Language Result Execution time Memory
198223 2020-01-25T07:16:32 Z Atalasion Beads and wires (APIO14_beads) C++14
0 / 100
 6 ms 5112 KB 
//khodaya khodet komak kon
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#define int long long

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 200000 + 10;
const ll MOD = 1000000000 + 7;
const ll INF = 1000000000000000000;
const ll LOG = 25;

int dp[N][2], n;
vector<pii> G[N];

void DFS(int v = 1, int p = 1){
	ll sm = 0;
	dp[v][1] = dp[v][0] = -INF;
	for (auto u:G[v]){
		if (u.F == p) continue;
		DFS(u.F, v);
		sm += max(dp[u.F][0], dp[u.F][1] + u.S);
	}
	for (auto u:G[v]){
		if (u.F == p) continue;
		dp[v][1] = max(dp[v][1], sm - max(dp[u.F][0], dp[u.F][1] + u.S) + u.S + dp[u.F][0]);
	}
	for (auto u:G[v]){
		for (auto x:G[v]){
			if (u.F == p || x.F == p) continue;
			if (u.F == x.F) continue;
			dp[v][0] = max(dp[v][0], sm - max(dp[u.F][0], dp[u.F][1] + u.S) - max(dp[x.F][0], dp[x.F][1] + x.S) + dp[u.F][0] + u.S + dp[x.F][0] + x.S);
		}
	}
	dp[v][0] = max(dp[v][0], sm);
	//cout << v << ' ' << dp[v][0] << ' ' << dp[v][1] << '\n';
}

int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	assert(n <= 10); 
	int ans = 0;
	for (int i = 0; i < n - 1; i++){
		int v, u, c;
		cin >> v >> u >> c;
		G[v].pb({u, c});
		G[u].pb({v, u});
	}
	for (int i = 1; i <= n; i++){
		DFS(i, i);
		ans = max(ans, dp[i][0]);
	}
	cout << ans;











	return 0;
}

Subtask #1
0 / 13.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 43.0

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