Submission #670145

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
670145	2022-12-08T07:46:10 Z	radal	Beads and wires (APIO14_beads)	C++17	57 / 100	1000 ms	7496 KB

beads

#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,avx2")
#pragma GCC optimize("unroll-loops,O2")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef pair<int,int> pll;
constexpr int N = 2e5+10,mod = 1e9+7,maxm = 210;
constexpr ll inf = 1e9+10;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
   // if (a+b < 0) return a+b+mod;
    return a+b;
}
 
inline int poww(int a,int k){
    if (k < 0) return 0;
    int z = 1;
    while (k){
        if (k&1) z = 1ll*z*a%mod;
        a = 1ll*a*a%mod;
        k >>= 1;
    } 
    return z; 
}
 
vector<pll> adj[N];
int dp[N][2];
 
void dfs(int v,int p){
	if ((int) adj[v].size() == 1 && p != 0){
		dp[v][1] = -2*inf;
		dp[v][0] = 0;
		return;
	}
	int s = 0,mx = -2*inf;
	for (auto [u,w] : adj[v]){
		if (u == p) continue;
		dfs(u,v);
		int val = max(dp[u][0],dp[u][1]+w);
		s += val;
		mx = max(mx,dp[u][0]-val+w);
	}
	dp[v][0] = s;
	dp[v][1] = s + mx;
}
 
bool cmp(int i,int j){
	return adj[i][0].Y > adj[j][0].Y;
}

int main(){
	ios :: sync_with_stdio(0); cin.tie(0); 
	int n;
	cin >> n;
	int mx = -1,U = -1,V = -1;
	rep(i,1,n){
		int u,v,w;
		cin >> u >> v >> w;
		if (w > mx){
			mx = w;
			U = u;
			V = v;
		}
		adj[u].pb({v,w});
		adj[v].pb({u,w});
	}
	if (n <= 2){
		cout << 0 << endl;
		return 0;
	}
	vector<int> leaf;
	rep(i,1,n+1){
		if ((int)adj[i].size() == 1) leaf.pb(i);
	}
	sort(all(leaf),cmp);
	int t = min(1800,(int)leaf.size()),ans = 0;
	rep(i,0,t){
	   	dfs(leaf[i],0);
		ans = max(ans,dp[leaf[i]][0]);
	}
	dfs(U,0);
	ans = max(ans,dp[U][0]);
	dfs(V,0);
	ans = max(ans,dp[V][0]);
	cout << ans;
}

Subtask #1
13.0 / 13.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	4948 KB	Output is correct
2	Correct	2 ms	4948 KB	Output is correct
3	Correct	2 ms	4948 KB	Output is correct
4	Correct	2 ms	4948 KB	Output is correct
5	Correct	2 ms	4948 KB	Output is correct
6	Correct	3 ms	4948 KB	Output is correct
7	Correct	2 ms	4948 KB	Output is correct
8	Correct	4 ms	4948 KB	Output is correct
9	Correct	3 ms	4948 KB	Output is correct
10	Correct	2 ms	4948 KB	Output is correct
11	Correct	2 ms	4904 KB	Output is correct
12	Correct	3 ms	4948 KB	Output is correct
13	Correct	3 ms	4948 KB	Output is correct
14	Correct	3 ms	4948 KB	Output is correct
15	Correct	3 ms	4948 KB	Output is correct
16	Correct	3 ms	4948 KB	Output is correct
17	Correct	3 ms	5076 KB	Output is correct
18	Correct	3 ms	4948 KB	Output is correct
19	Correct	3 ms	4948 KB	Output is correct
20	Correct	3 ms	4948 KB	Output is correct
21	Correct	3 ms	4948 KB	Output is correct
22	Correct	3 ms	4948 KB	Output is correct
23	Correct	151 ms	5260 KB	Output is correct
24	Correct	143 ms	5264 KB	Output is correct
25	Correct	145 ms	5260 KB	Output is correct
26	Correct	383 ms	5508 KB	Output is correct
27	Correct	386 ms	5512 KB	Output is correct
28	Correct	128 ms	5588 KB	Output is correct
29	Correct	118 ms	5588 KB	Output is correct
30	Correct	166 ms	5588 KB	Output is correct
31	Correct	395 ms	5868 KB	Output is correct

Subtask #4
0 / 43.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	4948 KB	Output is correct
2	Correct	2 ms	4948 KB	Output is correct
3	Correct	2 ms	4948 KB	Output is correct
4	Correct	2 ms	4948 KB	Output is correct
5	Correct	2 ms	4948 KB	Output is correct
6	Correct	3 ms	4948 KB	Output is correct
7	Correct	2 ms	4948 KB	Output is correct
8	Correct	4 ms	4948 KB	Output is correct
9	Correct	3 ms	4948 KB	Output is correct
10	Correct	2 ms	4948 KB	Output is correct
11	Correct	2 ms	4904 KB	Output is correct
12	Correct	3 ms	4948 KB	Output is correct
13	Correct	3 ms	4948 KB	Output is correct
14	Correct	3 ms	4948 KB	Output is correct
15	Correct	3 ms	4948 KB	Output is correct
16	Correct	3 ms	4948 KB	Output is correct
17	Correct	3 ms	5076 KB	Output is correct
18	Correct	3 ms	4948 KB	Output is correct
19	Correct	3 ms	4948 KB	Output is correct
20	Correct	3 ms	4948 KB	Output is correct
21	Correct	3 ms	4948 KB	Output is correct
22	Correct	3 ms	4948 KB	Output is correct
23	Correct	151 ms	5260 KB	Output is correct
24	Correct	143 ms	5264 KB	Output is correct
25	Correct	145 ms	5260 KB	Output is correct
26	Correct	383 ms	5508 KB	Output is correct
27	Correct	386 ms	5512 KB	Output is correct
28	Correct	128 ms	5588 KB	Output is correct
29	Correct	118 ms	5588 KB	Output is correct
30	Correct	166 ms	5588 KB	Output is correct
31	Correct	395 ms	5868 KB	Output is correct
32	Execution timed out	1098 ms	7496 KB	Time limit exceeded
33	Halted	0 ms	0 KB	-

Submission #670145

Compilation message

Subtask #1 13.0 / 13.0

Subtask #2 15.0 / 15.0

Subtask #3 29.0 / 29.0

Subtask #4 0 / 43.0

Subtask #1
13.0 / 13.0

Subtask #2
15.0 / 15.0

Subtask #3
29.0 / 29.0

Subtask #4
0 / 43.0