Submission #716881

#	Time	Username	Problem	Language	Result	Execution time	Memory
716881		vjudge1	Beads and wires (APIO14_beads)	C++17	0 / 100	55 ms	117724 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];
vector< ll > pref2[maxn];
vector< ll > suff2[maxn];

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

        sum1 = max(sum1 + max(dp[to][0], dp[to][1] + w), sum + dp[to][0] + w);
        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());

    reverse(suff2[v].begin(),  suff2[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]);
        ll up0 = max(dp0, dp1+w) + pref[v][i] + suff[v][i];
        up0 = max(dp0 + pref2[v][i]+suff[v][i] + w, up0);
        up0 = max(dp0 + pref[v][i]+suff2[v][i] + w, up0);
        calc(to, v, up0, pref[v][i] + suff[v][i] + dp0 + w);
        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);
    }

}

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 dfs(int, int)':
beads.cpp:18:17: warning: left shift count >= width of type [-Wshift-count-overflow]
   18 |     ll sum1 = -1<<50;
      |               ~~^~~~
beads.cpp: In function 'void calc(int, int, ll, ll)':
beads.cpp:54: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]
   54 |     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