Submission #34134

#	Time	Username	Problem	Language	Result	Execution time	Memory
34134		DoanPhuDuc	Beads and wires (APIO14_beads)	C++98	100 / 100	289 ms	21324 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 = 2e5 + 10;
const int INF = 0x3f3f3f3f;

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

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);
    }
    FOR(i, 0, 4) dp[u][i] = 0;
    // dp[u][0]
    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][1], dp[v][3]);
    }
    II best1 = II(-INF, -1), best2 = II(-INF, -1);
    REP(k, 0, adj[u].size()) {
        int v = adj[u][k].first, w = adj[u][k].second;
        if (v == p[u]) continue;
        int value = -max(dp[v][1], dp[v][3]) + w + dp[v][3];
        if (best1 == II(-INF, -1)) best1 = II(value, v);
            else if (best2 == II(-INF, -1)) {
                if (best1.first < value) {
                    best2 = best1;
                    best1 = II(value, v);
                } else best2 = II(value, v);
            } else {
                if (value > best1.first) {
                    best2 = best1;
                    best1 = II(value, v);
                } else if (value > best2.first) best2 = II(value, v);
              //  best2 = II(value, v);
              //  if (best1.first < best2.first) swap(best1, best2);
            }
    }
    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][1], dp[v1][3]) - max(dp[v2][1], dp[v2][3]);
            dp[u][0] = max(dp[u][0], newS + w1 + w2 + dp[v2][3]
                                   + max(dp[v1][0], dp[v1][4]));

        }*/
        dp[u][0] = max(dp[u][0], S - max(dp[v1][1], dp[v1][3]) + w1 + max(dp[v1][0], dp[v1][4])
                                   + (best1.second == v1 ? best2.first : best1.first));
    }

    //dp[u][1]
    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][1], dp[v][3]);
        dp[u][1] = max(dp[u][1], newS + dp[v][3] + w + a[u]);
    }

    // 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][1], dp[v][3]);
        dp[u][2] = max(dp[u][2], newS + max(dp[v][0], dp[v][4]) + w + a[u]);
    }

    // dp[u][3]
    dp[u][3] = S;

    // dp[u][4]
    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][1], dp[v][3]);
        int val = 0;
        FOR(i, 0, 4) val = max(val, dp[v][i]);
        dp[u][4] = max(dp[u][4], val + newS);
    }
}

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][0], max(dp[1][3], dp[1][4])));
    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:46: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:51:9:
     REP(k, 0, adj[u].size()) {
         ~~~~~~~~~~~~~~~~~~~             
beads.cpp:51: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:70:9:
     REP(k1, 0, adj[u].size()) {
         ~~~~~~~~~~~~~~~~~~~~            
beads.cpp:70: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:86:9:
     REP(k, 0, adj[u].size()) {
         ~~~~~~~~~~~~~~~~~~~             
beads.cpp:86: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:94:9:
     REP(k, 0, adj[u].size()) {
         ~~~~~~~~~~~~~~~~~~~             
beads.cpp:94: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:105:9:
     REP(k, 0, adj[u].size()) {
         ~~~~~~~~~~~~~~~~~~~             
beads.cpp:105:5: note: in expansion of macro 'REP'
     REP(k, 0, adj[u].size()) {
     ^~~
beads.cpp:106:34: warning: unused variable 'w' [-Wunused-variable]
         int v = adj[u][k].first, w = adj[u][k].second;
                                  ^
beads.cpp: In function 'int main()':
beads.cpp:120:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
beads.cpp:122: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: 13 / 13
• Subtask 2: 15 / 15
• Subtask 3: 29 / 29
• Subtask 4: 43 / 43