Submission #687748

#	Time	Username	Problem	Language	Result	Execution time	Memory
687748		beaboss	Beads and wires (APIO14_beads)	C++14	0 / 100	0 ms	212 KiB

beads

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

vector<pair<ll, ll> > topo;

// void dfs(ll i, vector<vector<ll> > &adj, vector<ll> &v) {
// 	topo.push_back(i);
// 	for (auto val: adj[i]) {
// 		if (!v[val]) {
// 			v[val] = true;
// 			dfs(val, adj, v);
// 		}
// 	}
// }

int main() {
	ll n;
	cin >> n;
	vector<vector<pair<ll, ll> > > adj(n);
	for (ll i = 0; i < n -1; i++) {
		ll a, b, w;
		cin >> a >> b >> w;
		a--;
		b--;
		adj[a].push_back({b, w});
		adj[b].push_back({a, w});
	}

	vector<bool> v(n, false);
	v[0] = true;

	queue<pair<ll, ll> > q;
	q.push({0, 0});
	v[0]= true;
	vector<ll> depth(n);
	depth[0] = 0;
	ll max_d;
	while (!q.empty()) {
		auto a = q.front();

		q.pop();
		topo.push_back(a);
		depth[a.first]=a.second;
		max_d = a.second;
		for (auto val: adj[a.first]) {
			if (!v[val.first]) {
				v[val.first]=true;
				q.push({val.first, a.second+1});
			}
		}
	}


	reverse(topo.begin(), topo.end());

	vector<ll> dp1(n, 0); // with i
	vector<ll> dp2(n, 0); // without i
	vector<ll> dp3(n, -1); // i with only 1 segment



	ll cur_depth = max_d;
	ll starting = 0;
	for (ll ind = 0; ind < n;ind++) {

		ll i = topo[ind].first;
		ll sum = 0;
		ll m1 = -10000000000000;
		ll m2= -10000000000000;

		ll maxi = -1000000000000;
		// ll sumofdp3 = 0;
		ll sumdp2 = 0;
		for (auto val: adj[i]) {
			if (depth[val.first] > depth[i]) {
				sumdp2 += dp1[val.first];
				ll maxpart;
				if (dp3[val.first] == -1) maxpart = dp1[val.first];
				else maxpart = max(dp1[val.first], dp3[val.first]+val.second);
				sum+=maxpart;
				ll contribution = dp1[val.first]+val.second - maxpart;
				if (contribution > m1) {
					m2 = m1;
					m1 = contribution;
				} else if (contribution > m2) {
					m2 = contribution;
				}
				// sumofdp3 += max(dp1[i], dp3[i]+val.second);
				// maxi = max(maxi, dp3[val.first]-dp1[val.first]+val.second);
			}
		}
		// if (i == 0) cout << sum << m1 << m2 << endl;
		// cout << i << ' ' << m1 << m2 << endl;
		if (m1+m2 >= 0) dp1[i] = max(dp1[i], sum + m1 + m2);
		else dp1[i] = max(dp1[i], sum);
		// dp1[i] = max(sumofdp3, dp1[i]);
		dp2[i] = max(dp2[i], sumdp2);
		dp3[i] = max(dp3[i], sum + m1);





	}
	// for (ll i=0; i < n;i++) cout << i << ' ';
	// 	cout << endl;
	// for (auto val: dp1) cout << val << ' ';
	// 	cout << endl;

	// for (auto val: dp2) cout << val << ' ';
	// 	cout << endl;
	// for (auto val: dp3) cout << val << ' ';
	// 	cout << endl;

	cout << max(dp1[0], dp2[0]) << endl;


}

Compilation message (stderr)

beads.cpp: In function 'int main()':
beads.cpp:73:6: warning: unused variable 'maxi' [-Wunused-variable]
   73 |   ll maxi = -1000000000000;
      |      ^~~~
beads.cpp:64:5: warning: unused variable 'cur_depth' [-Wunused-variable]
   64 |  ll cur_depth = max_d;
      |     ^~~~~~~~~
beads.cpp:65:5: warning: unused variable 'starting' [-Wunused-variable]
   65 |  ll starting = 0;
      |     ^~~~~~~~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 15
• Subtask 3: 0 / 29
• Subtask 4: 0 / 43