Submission #34101

#	Time	Username	Problem	Language	Result	Execution time	Memory
34101		DoanPhuDuc	Beads and wires (APIO14_beads)	C++98	0 / 100	4 ms	2688 KiB

beads

#include <bits/stdc++.h>

#define FOR(x, a, b) for (int x = a; x <= b; ++x)
#define FOD(x, a, b) for (int x = a; x >= b; --x)
#define REP(x, a, b) for (int x = a; x < b; ++x)
#define DEBUG(X) { cout << #X << " = " << X << endl; }
#define PR(A, n) { cout << #A << " = "; FOR(_, 1, n) cout << A[_] << " "; cout << endl; }
#define PR0(A, n)  { cout << #A << " = "; REP(_, 0, n) cout << A[_] << " "; cout << endl; }
#define BitCount(x) __builtin_popcount(x)

using namespace std;

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

const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;

int n;
int f[N], p[N], a[N];
int dp[N][4];

vector <II> adj[N];

void DFS(int u, int par = -1) {
    f[u] = -INF;
    REP(k, 0, adj[u].size()) {
        int v = adj[u][k].first, w = adj[u][k].second;
        if (v == par) continue;
        f[u] = max(f[u], w);
        p[v] = u; a[v] = w;
        DFS(v, u);
    }
}

void DP(int u) {
    REP(k, 0, adj[u].size()) {
        int v = adj[u][k].first, w = adj[u][k].second;
        if (v == p[u]) continue;
        DP(v);
    }
    dp[u][0] = dp[u][1] = 0;
    dp[u][2] = dp[u][3] = -INF;
    // dp[u][0]
    REP(k, 0, adj[u].size()) {
        int v = adj[u][k].first, w = adj[u][k].second;
        if (v == p[u]) continue;
        dp[u][0] += max(dp[v][0], max(dp[v][1], max(dp[v][2] + w, dp[v][3] + w)));
    }
    // dp[u][1]
    int S = 0;
    REP(k, 0, adj[u].size()) {
        int v = adj[u][k].first, w = adj[u][k].second;
        if (v == p[u]) continue;
        S += max(dp[v][0], max(dp[v][1], dp[v][2] + w));
    }
    REP(k1, 0, adj[u].size()) {
        int v1 = adj[u][k1].first, w1 = adj[u][k1].second;
        if (v1 == p[u]) continue;
        REP(k2, 0, adj[u].size()) if (k1 != k2) {
            int v2 = adj[u][k2].first, w2 = adj[u][k2].second;
            if (v2 == p[u]) continue;
            int newS = S - max(dp[v1][0], max(dp[v1][1], dp[v1][2] + w1))
                         - max(dp[v2][0], max(dp[v2][1], dp[v2][2] + w2));
            dp[u][1] = max(dp[u][1], dp[v1][0] + dp[v2][0] + w1 + w2 + newS);
            dp[u][1] = max(dp[u][1], dp[v1][1] + dp[v2][0] + w1 + w2 + newS);

            dp[u][2] = max(dp[u][2], dp[v1][0] + dp[v2][0] + w1 + w2 + newS);
            dp[u][2] = max(dp[u][2], dp[v1][1] + dp[v2][0] + w1 + w2 + newS);

            dp[u][3] = max(dp[u][3], dp[v1][1] + dp[v2][0] + w1 + w2 + newS);
        }
    }
    REP(k, 0, adj[u].size()) {
        int v = adj[u][k].first, w = adj[u][k].second;
        if (v == p[u]) continue;
        int newS = S - max(dp[v][0], max(dp[v][1], dp[v][2] + w));
        dp[u][1] = max(dp[u][1], dp[v][2] + w + newS);
    }
    // dp[u][2]
    REP(k, 0, adj[u].size()) {
        int v = adj[u][k].first, w = adj[u][k].second;
        if (v == p[u]) continue;
        int newS = S - max(dp[v][0], max(dp[v][1], dp[v][2] + w));
        dp[u][2] = max(dp[u][2], dp[v][0] + newS + w);
    }
    // dp[u][3]
    REP(k, 0, adj[u].size()) {
        int v = adj[u][k].first, w = adj[u][k].second;
        if (v == p[u]) continue;
        int newS = S - max(dp[v][0], max(dp[v][1], dp[v][2] + w));
        dp[u][3] = max(dp[u][3], dp[v][1] + newS + w);
    }
}

int main() {
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif // LOCAL
    scanf("%d", &n);
    FOR(i, 1, n - 1) {
        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);
    DP(1);
    printf("%d", max(dp[1][1], dp[1][0]));
    return 0;
}

Compilation message (stderr)

beads.cpp: In function 'void DFS(int, int)':
beads.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(x, a, b) for (int x = a; x < b; ++x)
beads.cpp:27:9:
     REP(k, 0, adj[u].size()) {
         ~~~~~~~~~~~~~~~~~~~             
beads.cpp:27:5: note: in expansion of macro 'REP'
     REP(k, 0, adj[u].size()) {
     ^~~
beads.cpp: In function 'void DP(int)':
beads.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(x, a, b) for (int x = a; x < b; ++x)
beads.cpp:37:9:
     REP(k, 0, adj[u].size()) {
         ~~~~~~~~~~~~~~~~~~~             
beads.cpp:37:5: note: in expansion of macro 'REP'
     REP(k, 0, adj[u].size()) {
     ^~~
beads.cpp:38:34: warning: unused variable 'w' [-Wunused-variable]
         int v = adj[u][k].first, w = adj[u][k].second;
                                  ^
beads.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(x, a, b) for (int x = a; x < b; ++x)
beads.cpp:45:9:
     REP(k, 0, adj[u].size()) {
         ~~~~~~~~~~~~~~~~~~~             
beads.cpp:45:5: note: in expansion of macro 'REP'
     REP(k, 0, adj[u].size()) {
     ^~~
beads.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(x, a, b) for (int x = a; x < b; ++x)
beads.cpp:52:9:
     REP(k, 0, adj[u].size()) {
         ~~~~~~~~~~~~~~~~~~~             
beads.cpp:52:5: note: in expansion of macro 'REP'
     REP(k, 0, adj[u].size()) {
     ^~~
beads.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(x, a, b) for (int x = a; x < b; ++x)
beads.cpp:57:9:
     REP(k1, 0, adj[u].size()) {
         ~~~~~~~~~~~~~~~~~~~~            
beads.cpp:57:5: note: in expansion of macro 'REP'
     REP(k1, 0, adj[u].size()) {
     ^~~
beads.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(x, a, b) for (int x = a; x < b; ++x)
beads.cpp:60:13:
         REP(k2, 0, adj[u].size()) if (k1 != k2) {
             ~~~~~~~~~~~~~~~~~~~~        
beads.cpp:60:9: note: in expansion of macro 'REP'
         REP(k2, 0, adj[u].size()) if (k1 != k2) {
         ^~~
beads.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(x, a, b) for (int x = a; x < b; ++x)
beads.cpp:74:9:
     REP(k, 0, adj[u].size()) {
         ~~~~~~~~~~~~~~~~~~~             
beads.cpp:74:5: note: in expansion of macro 'REP'
     REP(k, 0, adj[u].size()) {
     ^~~
beads.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(x, a, b) for (int x = a; x < b; ++x)
beads.cpp:81:9:
     REP(k, 0, adj[u].size()) {
         ~~~~~~~~~~~~~~~~~~~             
beads.cpp:81:5: note: in expansion of macro 'REP'
     REP(k, 0, adj[u].size()) {
     ^~~
beads.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(x, a, b) for (int x = a; x < b; ++x)
beads.cpp:88:9:
     REP(k, 0, adj[u].size()) {
         ~~~~~~~~~~~~~~~~~~~             
beads.cpp:88:5: note: in expansion of macro 'REP'
     REP(k, 0, adj[u].size()) {
     ^~~
beads.cpp: In function 'int main()':
beads.cpp:101:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
beads.cpp:103: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
• Subtask 2: 0 / 15
• Subtask 3: 0 / 29
• Subtask 4: 0 / 43