제출 #145200

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
145200		dolphingarlic	구슬과 끈 (APIO14_beads)	C++14	0 / 100	6 ms	5112 KiB

beads

#include <bits/stdc++.h>
#pragma GCC Optimize("O3")
#define FOR(i, x, y) for (int i = x; i < y; i++)
#define MOD 1000000007
typedef long long ll;
using namespace std;

vector<pair<int, int>> graph[200001];
int dp1[200001], dp2[200001], dp3[200001];

void dfs(int node, int parent, int edge) {
    int best = -1, second = -1;
    int best_val = INT_MIN, second_val = INT_MIN;

    for (pair<int, int> i : graph[node]) {
        if (i.first != parent) {
            dfs(i.first, node, i.second);

            dp1[node] += max(dp1[i.first], max(dp2[i.first], dp3[i.first]));

            if (max(dp1[i.first], dp2[i.first]) + i.second - dp3[i.first] > best_val) {
                second = best;
                second_val = best_val;
                
                best = i.first;
                best_val = max(dp1[i.first], dp2[i.first]) + i.second - dp3[i.first];
            } else if (max(dp1[i.first], dp2[i.first]) + i.second - dp3[i.first] > second_val) {
                second = i.first;
                second_val = max(dp1[i.first], dp2[i.first]) + i.second - dp3[i.first];
            }
        }
    }
    for (pair<int, int> i : graph[node]) {
        if (i.first != parent) {
            if (i.first == best) {
                dp2[node] += max(dp1[i.first], dp2[i.first]) + i.second;
                dp3[node] += max(dp1[i.first], dp2[i.first]) + i.second + edge;
            } else if (i.first == second) {
                dp2[node] += max(dp1[i.first], dp2[i.first]) + i.second;
                dp3[node] += max(dp1[i.first], max(dp2[i.first], dp3[i.first]));
            } else {
                dp2[node] += max(dp1[i.first], max(dp2[i.first], dp3[i.first]));
                dp3[node] += max(dp1[i.first], max(dp2[i.first], dp3[i.first]));
            }
        }
    }

    if (best == -1 || node == 1) dp3[node] = 0;
    if (second == -1) dp2[node] = 0;

    // cout << node << ' ' << dp1[node] << ' ' << dp2[node] << ' ' << dp3[node] << " | " << best << ' ' << second << '\n';
}

int main() {
    iostream::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    FOR(i, 1, n) {
        int a, b, c;
        cin >> a >> b >> c;
        graph[a].push_back({b, c});
        graph[b].push_back({a, c});
    }
    dfs(1, 0, 0);

    cout << max(dp1[1], dp2[1]) << '\n';
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

beads.cpp:2:0: warning: ignoring #pragma GCC Optimize [-Wunknown-pragmas]
 #pragma GCC Optimize("O3")

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