oj.uz

Submission #162289

# Submission time Handle Problem Language Result Execution time Memory
162289 2019-11-07T13:23:54 Z amoo_safar Beads and wires (APIO14_beads) C++14
57 / 100
 247 ms 3132 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;
typedef pair<pll, pll> node;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const ll Mod = 1000000007LL;
const int Maxn = 1e4 + 10;
const int Maxk = 60;
const ll Inf = 2242545357980376863LL;
const ll Log = 30;

vector<pll> G[Maxn];

ll dp1[Maxn], dp2[Maxn];

ll DFS(ll u, ll p){
	ll adj;
	ll mx = -Inf;
	for(auto ed : G[u]){
		adj = ed.F;
		if(adj == p) continue;
		DFS(adj, u);
		dp1[u] += max(dp1[adj], dp2[adj] + ed.S);
		mx = max(mx, ed.S + dp1[adj] - max(dp1[adj], dp2[adj] + ed.S));
	}
	dp2[u] = dp1[u] + mx;
}

ll dpu1[Maxn], dpu2[Maxn];
ll pssm[Maxn], psmx[Maxn];
ll sfsm[Maxn], sfmx[Maxn];
ll ans = 0;
ll dfs(ll u, ll p, ll w){
	vector< pair<pll, pll> > S;
	ll adj;
	for(auto ed : G[u]){
		adj = ed.F;
		if(adj == p){
			S.pb({{dpu1[u], dpu2[u]}, {w, adj}});
		} else {
			S.pb({{dp1[adj], dp2[adj]}, {ed.S, adj}});
		}
	}
	ll N = S.size();
	
	pssm[0] = 0;
	for(int i = 1; i <= N; i++) pssm[i] = pssm[i - 1] + max(S[i - 1].F.F, S[i - 1].F.S + S[i - 1].S.F);
	psmx[0] = -Inf;
	for(int i = 1; i <= N; i++) psmx[i] = max(psmx[i - 1] , S[i - 1].F.F + S[i - 1].S.F - max(S[i - 1].F.F, S[i - 1].F.S + S[i - 1].S.F) );
	reverse(all(S));
	swap(pssm, sfsm);
	swap(psmx, sfmx);
	
	pssm[0] = 0;
	for(int i = 1; i <= N; i++) pssm[i] = pssm[i - 1] + max(S[i - 1].F.F, S[i - 1].F.S + S[i - 1].S.F);
	psmx[0] = -Inf;
	for(int i = 1; i <= N; i++) psmx[i] = max(psmx[i - 1] , S[i - 1].F.F + S[i - 1].S.F - max(S[i - 1].F.F, S[i - 1].F.S + S[i - 1].S.F) );
	//if(u == 3) cerr << 
	ans = max(pssm[N], ans);
	
	for(int i = 0; i < N; i++){
		adj = S[i].S.S;
		if(adj == p) continue;
		dpu1[adj] = pssm[i] + sfsm[N - 1 - i];
		dpu2[adj] = dpu1[adj] + max(psmx[i], sfmx[N - 1 - i]);
	}
	
	for(auto ed : G[u]){
		adj = ed.F;
		if(adj != p) dfs(adj, u, ed.S);
	}
}


int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	ll n;
	cin >> n;
	ll u, v, w;
	for(int i = 1; i < n; i++){
		cin >> u >> v >> w;
		G[u].pb({v, w});
		G[v].pb({u, w});
	}
	DFS(1, -1);
	dfs(1, -1, 0);
	cout << ans;
	return 0;
}
/*
5
1 2 10
1 3 40
1 4 15
1 5 20

*/

Compilation message

beads.cpp: In function 'll DFS(ll, ll)':
beads.cpp:41:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
beads.cpp: In function 'll dfs(ll, ll, ll)':
beads.cpp:86:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

Subtask #1
13.0 / 13.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1016 KB Output is correct
2 Correct 3 ms 888 KB Output is correct
3 Correct 3 ms 888 KB Output is correct
4 Correct 3 ms 888 KB Output is correct
5 Correct 3 ms 888 KB Output is correct
6 Correct 3 ms 888 KB Output is correct
7 Correct 3 ms 892 KB Output is correct
8 Correct 3 ms 888 KB Output is correct
9 Correct 3 ms 888 KB Output is correct
10 Correct 3 ms 888 KB Output is correct
11 Correct 3 ms 888 KB Output is correct
12 Correct 3 ms 888 KB Output is correct
13 Correct 6 ms 888 KB Output is correct
14 Correct 5 ms 956 KB Output is correct
15 Correct 5 ms 888 KB Output is correct
16 Correct 8 ms 888 KB Output is correct
17 Correct 7 ms 888 KB Output is correct
18 Correct 8 ms 888 KB Output is correct
19 Correct 7 ms 1016 KB Output is correct
20 Correct 8 ms 888 KB Output is correct
21 Correct 7 ms 916 KB Output is correct
22 Correct 8 ms 1016 KB Output is correct
23 Correct 130 ms 1272 KB Output is correct
24 Correct 125 ms 1368 KB Output is correct
25 Correct 123 ms 1272 KB Output is correct
26 Correct 241 ms 1784 KB Output is correct
27 Correct 242 ms 1912 KB Output is correct
28 Correct 245 ms 2548 KB Output is correct
29 Correct 240 ms 2296 KB Output is correct
30 Correct 242 ms 2188 KB Output is correct
31 Correct 247 ms 3132 KB Output is correct

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1016 KB Output is correct
2 Correct 3 ms 888 KB Output is correct
3 Correct 3 ms 888 KB Output is correct
4 Correct 3 ms 888 KB Output is correct
5 Correct 3 ms 888 KB Output is correct
6 Correct 3 ms 888 KB Output is correct
7 Correct 3 ms 892 KB Output is correct
8 Correct 3 ms 888 KB Output is correct
9 Correct 3 ms 888 KB Output is correct
10 Correct 3 ms 888 KB Output is correct
11 Correct 3 ms 888 KB Output is correct
12 Correct 3 ms 888 KB Output is correct
13 Correct 6 ms 888 KB Output is correct
14 Correct 5 ms 956 KB Output is correct
15 Correct 5 ms 888 KB Output is correct
16 Correct 8 ms 888 KB Output is correct
17 Correct 7 ms 888 KB Output is correct
18 Correct 8 ms 888 KB Output is correct
19 Correct 7 ms 1016 KB Output is correct
20 Correct 8 ms 888 KB Output is correct
21 Correct 7 ms 916 KB Output is correct
22 Correct 8 ms 1016 KB Output is correct
23 Correct 130 ms 1272 KB Output is correct
24 Correct 125 ms 1368 KB Output is correct
25 Correct 123 ms 1272 KB Output is correct
26 Correct 241 ms 1784 KB Output is correct
27 Correct 242 ms 1912 KB Output is correct
28 Correct 245 ms 2548 KB Output is correct
29 Correct 240 ms 2296 KB Output is correct
30 Correct 242 ms 2188 KB Output is correct
31 Correct 247 ms 3132 KB Output is correct
32 Runtime error 3 ms 1016 KB Execution killed with signal 11 (could be triggered by violating memory limits)
33 Halted 0 ms 0 KB -