oj.uz

답안 #15851

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
15851 2015-07-31T11:34:34 Z myungwoo 구슬과 끈 (APIO14_beads) C++14
0 / 100
 16 ms 9728 KB 
#include <bits/stdc++.h>
using namespace std;

#define MAXN 200005
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()

int N;
int D[MAXN], E[MAXN], up[MAXN], V[MAXN];
vector <int> con[MAXN], conv[MAXN];

void dfs(int n, int from)
{
	vector <int> arr;
	for (int i=sz(con[n]);i--;){
		int t = con[n][i], v = conv[n][i];
		if (t == from) continue;
		up[t] = v; dfs(t, n);
		V[t] = D[t] - max(D[t], E[t]) + up[t];
		arr.pb(t);
	}
	sort(all(arr), [](const int &a, const int &b){
		return V[a] > V[b];
	});
	D[n] = E[n] = 0;
	if (arr.empty()) return;
	for (int t: arr) D[n] += max(D[t], E[t]);
	E[n] = D[n];
	if (sz(arr) > 1)
		D[n] += max(0, V[arr[0]] + V[arr[1]]);
	E[n] += up[n] + V[arr[0]];
}

int main()
{
	scanf("%d", &N);
	for (int i=1;i<N;i++){
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		con[a].pb(b); conv[a].pb(c);
		con[b].pb(a); conv[b].pb(c);
	}
	dfs(1, 0);
	printf("%d\n", D[1]);
}

Compilation message

beads.cpp: In function 'int main()':
beads.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
beads.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &a, &b, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 9728 KB Output is correct
2 Correct 10 ms 9728 KB Output is correct
3 Correct 11 ms 9728 KB Output is correct
4 Correct 16 ms 9728 KB Output is correct
5 Correct 10 ms 9728 KB Output is correct
6 Incorrect 9 ms 9728 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 9728 KB Output is correct
2 Correct 10 ms 9728 KB Output is correct
3 Correct 11 ms 9728 KB Output is correct
4 Correct 16 ms 9728 KB Output is correct
5 Correct 10 ms 9728 KB Output is correct
6 Incorrect 9 ms 9728 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 9728 KB Output is correct
2 Correct 10 ms 9728 KB Output is correct
3 Correct 11 ms 9728 KB Output is correct
4 Correct 16 ms 9728 KB Output is correct
5 Correct 10 ms 9728 KB Output is correct
6 Incorrect 9 ms 9728 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 9728 KB Output is correct
2 Correct 10 ms 9728 KB Output is correct
3 Correct 11 ms 9728 KB Output is correct
4 Correct 16 ms 9728 KB Output is correct
5 Correct 10 ms 9728 KB Output is correct
6 Incorrect 9 ms 9728 KB Output isn't correct
7 Halted 0 ms 0 KB -