Submission #550393

#	Time	Username	Problem	Language	Result	Execution time	Memory
550393		Duy_e	Beads and wires (APIO14_beads)	C++14	100 / 100	346 ms	45916 KiB

beads

/*
**  TASK:
**  LINK:
*/

#include <bits/stdc++.h>
#define ll long long
#define pii pair<ll, ll>
#define st first
#define nd second
#define file "test"
using namespace std;
const long long INF = 1e18;
const long long N = 2e5 + 5;

struct edge {
    ll u, v, w;
} g[N];

vector <int> d[N];

int n;
ll dp[N][2], dp2[N][2], ans;

/*
    0: là node được nối với dây đỏ
    1: là node được thêm sau 2 node trước
*/

void dfs(int p, int u) {

    ll s0 = 0;
    vector <ll> f; f.push_back(0);
    for (int i: d[u]) {
        int v = g[i].u ^ g[i].v ^ u;
        int w = g[i].w;
        if (v == p) continue;
        dfs(u, v);
        s0 += dp[v][0];
        f.push_back(f.back() + max(dp[v][0], dp[v][1] + w));
    }

    f.push_back(f.back());

    dp[u][0] = s0;
    int pos = 1;
    for (int i: d[u]) {
        int v = g[i].u ^ g[i].v ^ u;
        int w = g[i].w;

        if (v == p) continue;

        dp[u][1] = max(dp[u][1], f[pos - 1] + f[f.size() - 1] - f[pos] + dp[v][0] + w);
        dp[u][0] = max(dp[u][0] + dp[v][1] + w - dp[v][0], dp[u][0]);
        pos ++;
    }

    // cout << u << ": " << dp[u][0] << ' ' << dp[u][1] << ' ' << d[u].size() << '\n';

    dp2[u][0] = dp[u][0];
    dp2[u][1] = dp[u][1];

}

void dfs_reroot(int p, int u) {
    vector <ll> f, lef, rig;
    f.push_back(0);

    ll s0 = 0;

    //cout << u << ": " << dp2[u][0] << ' ' << dp2[u][1] <<
    //"; " << p << ": " << dp2[p][0] << ' ' << dp2[p][1] << '\n';

    for (int i: d[u]) {
        int v = g[i].v ^ g[i].u ^ u;
        int w = g[i].w;
        s0 += dp2[v][0];
        f.push_back(f.back() + max(dp2[v][0], dp2[v][1] + w));
    }

    dp2[u][0] = s0;
    dp2[u][1] = -INF;
    f.push_back(f.back());
    lef.push_back(0);
    int pos = 1;
    for (int i: d[u]) {
        int v = g[i].v ^ g[i].u ^ u;
        int w = g[i].w;
        dp2[u][0] = max(dp2[u][0], dp2[u][0] - dp2[v][0] + dp2[v][1] + w);
        dp2[u][1] = max(dp2[u][1], f[pos - 1] + f[f.size() - 1] - f[pos] + dp2[v][0] + w);
        lef.push_back(f[pos - 1] + f[f.size() - 1] - f[pos] + dp2[v][0] + w);
        pos ++;
    }

    //cout << u << ": " << dp2[u][0] << ' ' << dp2[u][1] << '\n';

    ans = max(ans, dp2[u][0]);

    lef.push_back(0);
    rig = lef;

    for (int i = 1; i < lef.size(); i ++) lef[i] = max(lef[i - 1], lef[i]);
    for (int i = rig.size() - 2; i >= 0; i --) rig[i] = max(rig[i + 1], rig[i]);

    pos = 1;

    for (int i: d[u]) {
        int v = g[i].u ^ g[i].v ^ u;
        int w = g[i].w;

        ll tmp1 = dp2[u][1], tmp0 = dp2[u][0];

        dp2[u][0] -= max(dp[v][0], dp[v][1] + w);
        dp2[u][1] = max(lef[pos - 1], rig[pos + 1]) - max(dp2[v][0], dp2[v][1] + w);
        if (p != v) dfs_reroot(u, v);

        dp2[u][1] = tmp1; dp2[u][0] = tmp0;
        pos ++;
    }

    dp2[u][0] = dp[u][0];
    dp2[u][1] = dp[u][1];

}


int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
     //#ifndef ONLINE_JUDGE
     //    freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
     //#endif

    cin >> n;
    for (int i = 1; i < n; i ++) {
        cin >> g[i].u >> g[i].v >> g[i].w;
        d[g[i].u].push_back(i);
        d[g[i].v].push_back(i);
    }

//    for (int i = 1; i <= n; i ++) {
//        for (int j = 0; j <= n; j ++)
//            dp[j][0] = dp[j][1] = -INF;
//        dfs(0, i);
//
//        ans = max(ans, dp[i][0]);
//        // cout << i << ' ' << dp[i][0] << '\n';
//    }

    for (int i = 0; i <= n; i ++)
        for (int j = 0; j <= 1; j ++)
            dp[i][j] = dp2[i][j] = -INF;

    dfs(0, 1);
    dfs_reroot(0, 1);
    cout << ans;

    return 0;
}
/**  /\_/\
*   (= ._.)
*   / >🍵 \>🍮

1 node chỉ có thể được nối với tối đa là 2 dây xanh và chỉ có thể có đúng 2 dây xanh liên tiếp?



2 thao tác:
+ append(w, v): gắn nút w mới vào một nút v "ĐÃ TỒN TẠI"
-> nếu fix root của 1 subtree root v thì v không thể được thêm vào sau 2 nút con được

+ insert(w, u, v): gắn nút w mới vào giữa 2 nút u, v "ĐÃ TỒN TẠI"

3 sub đầu dp n ^ 2 -> solve for each root

**/

Compilation message (stderr)

beads.cpp:160:9: warning: "/*" within comment [-Wcomment]
  160 | /**  /\_/\
      |          
beads.cpp: In function 'void dfs_reroot(int, int)':
beads.cpp:102:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for (int i = 1; i < lef.size(); i ++) lef[i] = max(lef[i - 1], lef[i]);
      |                     ~~^~~~~~~~~~~~

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