답안 #106072

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
106072 2019-04-16T11:17:41 Z Saboon 구슬과 끈 (APIO14_beads) C++14
28 / 100
1000 ms 5504 KB
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 2e5 + 10;
const int inf = 1e8;

int dp[maxn], pd[maxn];
vector<pair<int, int> > t[maxn];

void dfs(int v, int par = -1){
	int mx = -inf;
	dp[v] = 0;
	for (auto edge : t[v]){
		int u = edge.first, c = edge.second;
		if (u != par){
			dfs(u, v);
			dp[v] += max(dp[u], pd[u] + c);
			mx = max(mx, dp[u] + c - max(dp[u], pd[u] + c)); 
		}
	}
	pd[v] = dp[v] + mx;
}

int main(){
	ios_base::sync_with_stdio (false);
	int n;
	cin >> n;
	for (int i = 1; i <= n - 1; i++){
		int v, u, c;
		cin >> v >> u >> c;
		t[v].push_back({u, c});
		t[u].push_back({v, c});
	}
	int answer = 0;
	for (int v = 1; v <= n; v++){
		dfs(v);
		answer = max(answer, dp[v]);
	}
	cout << answer << endl;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 5120 KB Output is correct
2 Correct 6 ms 5120 KB Output is correct
3 Correct 6 ms 5120 KB Output is correct
4 Correct 6 ms 4992 KB Output is correct
5 Correct 6 ms 5120 KB Output is correct
6 Correct 6 ms 5120 KB Output is correct
7 Correct 6 ms 5120 KB Output is correct
8 Correct 6 ms 5120 KB Output is correct
9 Correct 6 ms 5120 KB Output is correct
10 Correct 6 ms 5120 KB Output is correct
11 Correct 6 ms 5120 KB Output is correct
12 Correct 6 ms 5120 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 5120 KB Output is correct
2 Correct 6 ms 5120 KB Output is correct
3 Correct 6 ms 5120 KB Output is correct
4 Correct 6 ms 4992 KB Output is correct
5 Correct 6 ms 5120 KB Output is correct
6 Correct 6 ms 5120 KB Output is correct
7 Correct 6 ms 5120 KB Output is correct
8 Correct 6 ms 5120 KB Output is correct
9 Correct 6 ms 5120 KB Output is correct
10 Correct 6 ms 5120 KB Output is correct
11 Correct 6 ms 5120 KB Output is correct
12 Correct 6 ms 5120 KB Output is correct
13 Correct 6 ms 5120 KB Output is correct
14 Correct 6 ms 4992 KB Output is correct
15 Correct 6 ms 4992 KB Output is correct
16 Correct 7 ms 5120 KB Output is correct
17 Correct 6 ms 4992 KB Output is correct
18 Correct 6 ms 4992 KB Output is correct
19 Correct 6 ms 4992 KB Output is correct
20 Correct 6 ms 5120 KB Output is correct
21 Correct 6 ms 4992 KB Output is correct
22 Correct 6 ms 5120 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 5120 KB Output is correct
2 Correct 6 ms 5120 KB Output is correct
3 Correct 6 ms 5120 KB Output is correct
4 Correct 6 ms 4992 KB Output is correct
5 Correct 6 ms 5120 KB Output is correct
6 Correct 6 ms 5120 KB Output is correct
7 Correct 6 ms 5120 KB Output is correct
8 Correct 6 ms 5120 KB Output is correct
9 Correct 6 ms 5120 KB Output is correct
10 Correct 6 ms 5120 KB Output is correct
11 Correct 6 ms 5120 KB Output is correct
12 Correct 6 ms 5120 KB Output is correct
13 Correct 6 ms 5120 KB Output is correct
14 Correct 6 ms 4992 KB Output is correct
15 Correct 6 ms 4992 KB Output is correct
16 Correct 7 ms 5120 KB Output is correct
17 Correct 6 ms 4992 KB Output is correct
18 Correct 6 ms 4992 KB Output is correct
19 Correct 6 ms 4992 KB Output is correct
20 Correct 6 ms 5120 KB Output is correct
21 Correct 6 ms 4992 KB Output is correct
22 Correct 6 ms 5120 KB Output is correct
23 Correct 641 ms 5368 KB Output is correct
24 Correct 653 ms 5220 KB Output is correct
25 Correct 628 ms 5340 KB Output is correct
26 Execution timed out 1083 ms 5504 KB Time limit exceeded
27 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 5120 KB Output is correct
2 Correct 6 ms 5120 KB Output is correct
3 Correct 6 ms 5120 KB Output is correct
4 Correct 6 ms 4992 KB Output is correct
5 Correct 6 ms 5120 KB Output is correct
6 Correct 6 ms 5120 KB Output is correct
7 Correct 6 ms 5120 KB Output is correct
8 Correct 6 ms 5120 KB Output is correct
9 Correct 6 ms 5120 KB Output is correct
10 Correct 6 ms 5120 KB Output is correct
11 Correct 6 ms 5120 KB Output is correct
12 Correct 6 ms 5120 KB Output is correct
13 Correct 6 ms 5120 KB Output is correct
14 Correct 6 ms 4992 KB Output is correct
15 Correct 6 ms 4992 KB Output is correct
16 Correct 7 ms 5120 KB Output is correct
17 Correct 6 ms 4992 KB Output is correct
18 Correct 6 ms 4992 KB Output is correct
19 Correct 6 ms 4992 KB Output is correct
20 Correct 6 ms 5120 KB Output is correct
21 Correct 6 ms 4992 KB Output is correct
22 Correct 6 ms 5120 KB Output is correct
23 Correct 641 ms 5368 KB Output is correct
24 Correct 653 ms 5220 KB Output is correct
25 Correct 628 ms 5340 KB Output is correct
26 Execution timed out 1083 ms 5504 KB Time limit exceeded
27 Halted 0 ms 0 KB -