oj.uz

Submission #439664

# Submission time Handle Problem Language Result Execution time Memory
439664 2021-06-30T13:37:25 Z soroush Beads and wires (APIO14_beads) C++17
57 / 100
 8 ms 1484 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int , int> pii;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 1e4 + 10;
const ll mod = 1e9+7;

#define pb push_back
#define endl '\n'
#define dokme(x) cout << x , exit(0)
#define ms(x , y) memset(x , y , sizeof x)
ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);}

int n;
int dp[maxn][2] , ans;
vector < pii > adj[maxn];

void dfs(int v , int par = 0){
	for(auto [u , w] : adj[v])if(u ^ par)
		dfs(u , v),
		dp[v][0] += max(dp[u][0] , dp[u][1] + w);
	dp[v][1] = -2e9 - 10;
	for(auto [u , w] : adj[v])if(u ^ par)
		dp[v][1] = max(dp[v][1] , dp[v][0] + w + dp[u][0] - max(dp[u][0] , dp[u][1] + w));
}

void solve(int v , int par = 0){
	ans = max(ans , dp[v][0]);
	int mx[2] = {int(-2e9 - 10) , int(-2e9 - 10)};
	for(auto [u , w] : adj[v]){
		mx[1] = max(mx[1] , dp[u][0] + w - max(dp[u][1] + w , dp[u][0]));
		if(mx[0] < mx[1])swap(mx[0] , mx[1]);
	}
	for(auto [u , w] : adj[v])if(u ^ par){
		int a = dp[u][1] , b = dp[u][0] , c = dp[v][0] , d = dp[v][1];
		bool imx = w + dp[u][0] - max(dp[u][0] , dp[u][1] + w) == mx[0];
		dp[v][1] -= max(dp[u][0] , dp[u][1] + w);
		if(imx)dp[v][1] += mx[1] - mx[0];
		dp[v][0] -= max(dp[u][0] , dp[u][1] + w);
		dp[u][1] += max(dp[v][0] , dp[v][1] + w);
		dp[u][1] = max(dp[u][1] , dp[u][0] + w + dp[v][0]);
		dp[u][0] += max(dp[v][0] , dp[v][1] + w);
		solve(u , v);
		dp[u][1] = a , dp[u][0] = b , dp[v][0] = c , dp[v][1] = d;
	}
}

int32_t main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin >> n;
	for(int i = 1 ; i < n ; i ++){
		int a , b , c;
		cin >> a >> b >> c;
		adj[a].pb({b , c});
		adj[b].pb({a , c});
	}
	dfs(1);
	solve(1);
	cout << ans;
	return(0);
}

Subtask #1
13.0 / 13.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Correct 1 ms 460 KB Output is correct
14 Correct 1 ms 460 KB Output is correct
15 Correct 1 ms 460 KB Output is correct
16 Correct 1 ms 460 KB Output is correct
17 Correct 1 ms 460 KB Output is correct
18 Correct 1 ms 460 KB Output is correct
19 Correct 1 ms 460 KB Output is correct
20 Correct 1 ms 460 KB Output is correct
21 Correct 1 ms 460 KB Output is correct
22 Correct 1 ms 460 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Correct 1 ms 460 KB Output is correct
14 Correct 1 ms 460 KB Output is correct
15 Correct 1 ms 460 KB Output is correct
16 Correct 1 ms 460 KB Output is correct
17 Correct 1 ms 460 KB Output is correct
18 Correct 1 ms 460 KB Output is correct
19 Correct 1 ms 460 KB Output is correct
20 Correct 1 ms 460 KB Output is correct
21 Correct 1 ms 460 KB Output is correct
22 Correct 1 ms 460 KB Output is correct
23 Correct 3 ms 716 KB Output is correct
24 Correct 3 ms 716 KB Output is correct
25 Correct 3 ms 716 KB Output is correct
26 Correct 6 ms 956 KB Output is correct
27 Correct 8 ms 1108 KB Output is correct
28 Correct 5 ms 1228 KB Output is correct
29 Correct 5 ms 1180 KB Output is correct
30 Correct 5 ms 1100 KB Output is correct
31 Correct 6 ms 1484 KB Output is correct

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Correct 1 ms 460 KB Output is correct
14 Correct 1 ms 460 KB Output is correct
15 Correct 1 ms 460 KB Output is correct
16 Correct 1 ms 460 KB Output is correct
17 Correct 1 ms 460 KB Output is correct
18 Correct 1 ms 460 KB Output is correct
19 Correct 1 ms 460 KB Output is correct
20 Correct 1 ms 460 KB Output is correct
21 Correct 1 ms 460 KB Output is correct
22 Correct 1 ms 460 KB Output is correct
23 Correct 3 ms 716 KB Output is correct
24 Correct 3 ms 716 KB Output is correct
25 Correct 3 ms 716 KB Output is correct
26 Correct 6 ms 956 KB Output is correct
27 Correct 8 ms 1108 KB Output is correct
28 Correct 5 ms 1228 KB Output is correct
29 Correct 5 ms 1180 KB Output is correct
30 Correct 5 ms 1100 KB Output is correct
31 Correct 6 ms 1484 KB Output is correct
32 Runtime error 1 ms 952 KB Execution killed with signal 11
33 Halted 0 ms 0 KB -