oj.uz

답안 #687580

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
687580 2023-01-26T15:28:55 Z beaboss 구슬과 끈 (APIO14_beads) C++14
0 / 100
 1 ms 212 KB 
#include <bits/stdc++.h>

using namespace std;

vector<pair<int, int> > topo;

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

int main() {
	int n;
	cin >> n;
	vector<vector<pair<int, int> > > adj(n);
	for (int i = 0; i < n -1; i++) {
		int 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<int, int> > q;
	q.push({0, 0});
	v[0]= true;
	vector<int> depth(n);
	depth[0] = 0;
	int 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<int> dp1(n, 0); // with i
	vector<int> dp2(n, 0); // without i
	vector<int> dp3(n, -1); // i with only 1 segment



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

		int i = topo[ind].first;
		int sum = 0;
		int m1 = -100000000;
		int m2= -100000000;

		int maxi = -10000000;
		// int sumofdp3 = 0;
		int sumdp2 = 0;
		for (auto val: adj[i]) {
			if (depth[val.first] > depth[i]) {
				sumdp2 += dp1[val.first];
				int maxpart;
				if (dp3[val.first] == -1) maxpart = dp1[val.first];
				else maxpart = max(dp1[val.first], dp3[val.first]+val.second);
				sum+=maxpart;
				int 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);
			}
		}
		// if (i == 0) cout << sum << m1 << m2 << endl;
		dp1[i] = max(dp1[i], sum + m1 + m2);
		// dp1[i] = max(sumofdp3, dp1[i]);
		dp2[i] = max(dp2[i], sumdp2);
		dp3[i] = max(dp3[i], sum + m1);





	}
	// for (int 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

beads.cpp: In function 'int main()':
beads.cpp:72:7: warning: unused variable 'maxi' [-Wunused-variable]
   72 |   int maxi = -10000000;
      |       ^~~~
beads.cpp:63:6: warning: unused variable 'cur_depth' [-Wunused-variable]
   63 |  int cur_depth = max_d;
      |      ^~~~~~~~~
beads.cpp:64:6: warning: unused variable 'starting' [-Wunused-variable]
   64 |  int starting = 0;
      |      ^~~~~~~~

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -