Submission #716880

#	Time	Username	Problem	Language	Result	Execution time	Memory
716880		vjudge1	Beads and wires (APIO14_beads)	C++17	0 / 100	35 ms	70740 KiB

beads

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
const int maxn = 1e6 + 100;
const int mod = (int)1e9+7;
int n;
vector<pair<int, int> > g[maxn];
vector< ll > pref[maxn];
vector< ll > suff[maxn];

ll dp[maxn][2];
void dfs(int v, int p) {
    ll sum = 0;
    for(auto[to, w]: g[v]) {
        pref[v].push_back(sum);
        if(to == p) {
            continue;
        }
        dfs(to, v);
        sum += max(dp[to][0], dp[to][1] + w);
    }
    dp[v][0] = sum;
    sum = 0;
    dp[v][1] = -(1ll<<50);
    for(int i = (int)g[v].size() - 1; i >= 0; i--) {
        int to = g[v][i].first;
        suff[v].push_back(sum);
        if(to == p) continue;
        dp[v][1] = max(dp[v][1], sum + pref[v][i] + g[v][i].second + dp[to][0]);
        sum += max(dp[to][0], dp[to][1] + g[v][i].second);
    }
    reverse(suff[v].begin(),  suff[v].end());
}
ll ans;
void calc(int v, int p, ll dp0, ll dp1) {
    ans = max(ans, dp[v][0] + dp0);

    ll sum1 = dp0;
    ll sum2 = dp1;
    for(int i = 0;i < g[v].size(); i++) {
        int to = g[v][i].first;
        int w = g[v][i].second;
        if(to == p) continue;

        ans = max(ans, sum2 + w + suff[v][i] + dp[to][0]);
        sum2 = max(sum2 + max(dp[to][0], dp[to][1] + w), sum1 + dp[to][0] + w);
        sum1 += max(dp[to][0], dp[to][1] + w);
        calc(to, v, max(dp0, dp1+w) + pref[v][i] + suff[v][i], pref[v][i] + suff[v][i] + dp0 + w);
    }

}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for(int i = 1; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    dfs(1, 0);
    calc(1, 0, 0, -(1ll<<50));
    cout << ans << "\n";
}

Compilation message (stderr)

beads.cpp: In function 'void calc(int, int, ll, ll)':
beads.cpp:42:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(int i = 0;i < g[v].size(); i++) {
      |                   ~~^~~~~~~~~~~~~

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