oj.uz

답안 #23718

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
23718 2017-05-22T17:29:12 Z abcdef6199 구슬과 끈 (APIO14_beads) C++
0 / 100
 6 ms 4992 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> II;

const int N = (int) 2e5 + 10;
int n, dp[N][2];
vector<II> adj[N];

void DFS(int u, int p = -1) {
    if ((int) adj[u].size() == 1 && adj[u][0].first == p) {
        dp[u][0] = 0;
        dp[u][1] = -2e9;
        return;
    }
    vector<int> delta;
    for (int i = 0; i < (int) adj[u].size(); ++i) {
        int v = adj[u][i].first;
        int w = adj[u][i].second;
        if (v != p) {
            DFS(v, u);
            int f = max(dp[v][0], w + dp[v][1]);
            dp[u][0] += f;
            dp[u][1] += f;
            delta.push_back(w + dp[v][0] - f);
        }
    }
    sort(delta.begin(), delta.end(), greater<int>());
    dp[u][1] += delta[0];
    if (delta.size() >= 2) dp[u][0] += delta[0] + delta[1];
}

int main() {
#ifdef LOCAL
    freopen("inp", "r", stdin);
    freopen("out", "w", stdout);
#endif
    scanf("%d", &n);
    for (int i = 1; i <= n - 1; ++i) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        adj[u].push_back(II(v, w));
        adj[v].push_back(II(u, w));
    }

    DFS(1);
    printf("%d", dp[1][0]);
    return 0;
}

Compilation message

beads.cpp: In function 'int main()':
beads.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
beads.cpp:41:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int u, v, w; scanf("%d%d%d", &u, &v, &w);
                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 43.0

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