oj.uz

Submission #36583

# Submission time Handle Problem Language Result Execution time Memory
36583 2017-12-11T11:55:12 Z letrongdat Beads and wires (APIO14_beads) C++14
0 / 100
 6 ms 5120 KB 
#include <bits/stdc++.h>

using namespace std;

inline int read()
{
    char c;
    int sign = 1;
    do { c = getchar(); } while (c < '0' || c > '9');
    int res;
    for(res = 0; c >= '0' && c <= '9'; c = getchar())
        res = res * 10 + c -'0';
    return res;
}
#define ii pair < int, int >
#define ft first
#define nd second
#define int long long
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define REP(i, a, b) for(int i = a; i  < b; ++i)
const int N = 2e5 +10;
int dp[N][4];
int f[N];
int n;
vector < ii > adj[N];
bool cmp(ii a, ii b)
{
    return a.nd + max(dp[a.ft][0], dp[a.ft][2]) - f[a.ft] > b.nd + max(dp[b.ft][0], dp[b.ft][2]) - f[b.ft];
}
void dfs(int u, int prv = 0, int dd = 0)
{
    FOR(i, 0, 2) dp[u][i] = 0;
    int S = 0;
    REP(i, 0, adj[u].size())
    {
        int v = adj[u][i].first, d = adj[u][i].second;
        if (v == prv) continue;
        dfs(v, u, d);
        dp[u][0] += f[v];
        S += max(dp[v][0], dp[v][1]);
    }
    vector < ii > vt;
    REP(i, 0, adj[u].size())
    {
        int v = adj[u][i].first, d = adj[u][i].second;
        if (v == prv) continue;
        vt.push_back({v, d});
        if (prv != 0)
        {
            dp[u][1] = max(dp[u][1], dd + d + S - max(dp[v][0], dp[v][1]) + max(dp[v][0], dp[v][2]));
        }
    }
    if (vt.size() > 1)
    {
        dp[u][2] = dp[u][0];
        sort(vt.begin(), vt.end(), cmp);
        FOR(i, 0, 1)
        {
            dp[u][2] += vt[i].nd + max(dp[vt[i].ft][0], dp[vt[i].ft][2]) - f[vt[i].ft];
        }

    }

    FOR(i, 0, 2) f[u] = max(f[u], dp[u][i]);
}
main()
{

    n = read();
    REP(i, 1, n)
    {
        int u, v, d;
        cin >> u >> v >> d;
        adj[u].push_back({v, d});
        adj[v].push_back({u, d});
    }
    dfs(1);
    cout << f[1];
}

Compilation message

beads.cpp: In function 'int read()':
beads.cpp:8:9: warning: unused variable 'sign' [-Wunused-variable]
     int sign = 1;
         ^~~~
beads.cpp: In function 'void dfs(long long int, long long int, long long int)':
beads.cpp:20:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i, a, b) for(int i = a; i  < b; ++i)
beads.cpp:34:9:
     REP(i, 0, adj[u].size())
         ~~~~~~~~~~~~~~~~~~~             
beads.cpp:34:5: note: in expansion of macro 'REP'
     REP(i, 0, adj[u].size())
     ^~~
beads.cpp:20:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i, a, b) for(int i = a; i  < b; ++i)
beads.cpp:43:9:
     REP(i, 0, adj[u].size())
         ~~~~~~~~~~~~~~~~~~~             
beads.cpp:43:5: note: in expansion of macro 'REP'
     REP(i, 0, adj[u].size())
     ^~~
beads.cpp: At global scope:
beads.cpp:66:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4992 KB Output is correct
2 Correct 6 ms 4992 KB Output is correct
3 Correct 6 ms 4992 KB Output is correct
4 Correct 6 ms 5120 KB Output is correct
5 Correct 5 ms 4992 KB Output is correct
6 Incorrect 5 ms 4992 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4992 KB Output is correct
2 Correct 6 ms 4992 KB Output is correct
3 Correct 6 ms 4992 KB Output is correct
4 Correct 6 ms 5120 KB Output is correct
5 Correct 5 ms 4992 KB Output is correct
6 Incorrect 5 ms 4992 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4992 KB Output is correct
2 Correct 6 ms 4992 KB Output is correct
3 Correct 6 ms 4992 KB Output is correct
4 Correct 6 ms 5120 KB Output is correct
5 Correct 5 ms 4992 KB Output is correct
6 Incorrect 5 ms 4992 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4992 KB Output is correct
2 Correct 6 ms 4992 KB Output is correct
3 Correct 6 ms 4992 KB Output is correct
4 Correct 6 ms 5120 KB Output is correct
5 Correct 5 ms 4992 KB Output is correct
6 Incorrect 5 ms 4992 KB Output isn't correct
7 Halted 0 ms 0 KB -