oj.uz

Submission #158434

# Submission time Handle Problem Language Result Execution time Memory
158434 2019-10-17T04:19:38 Z mhy908 Beads and wires (APIO14_beads) C++14
0 / 100
 6 ms 5112 KB 
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define inf 1987654321
using namespace std;
typedef long long LL;
int n;
LL dp1[200010], dp2[200010], dp3[200010], dp[200010];
vector<pair<int, LL> > link[200010];
void get_dp(int num, int par, LL c)
{
    LL sum=0;
    vector<LL> comp;
    for(int i=0; i<link[num].size(); i++){
        if(par==link[num][i].F)continue;
        get_dp(link[num][i].F, num, link[num][i].S);
        sum+=dp[link[num][i].F];
        comp.pb(-dp[link[num][i].F]+max(dp3[link[num][i].F], dp2[link[num][i].F])+link[num][i].S);
        dp3[num]=max(dp3[num], dp[link[num][i].F]);
    }
    sort(comp.begin(), comp.end(), greater<LL>());
    if(comp.size()>=1)dp1[num]=sum+comp[0]+c;
    if(comp.size()>=2)dp2[num]=sum+comp[0]+comp[1];
    dp[num]=max(dp3[num], max(dp1[num], dp2[num]));
}
int main()
{
    scanf("%d", &n);
    for(int i=1; i<n; i++){
        int a, b;
        LL c;
        scanf("%d %d %lld", &a, &b, &c);
        link[a].pb(mp(b, c));
        link[b].pb(mp(a, c));
    }
    get_dp(1, 0, -inf);
    printf("%lld", dp[1]);
}

Compilation message

beads.cpp: In function 'void get_dp(int, int, LL)':
beads.cpp:16:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<link[num].size(); i++){
                  ~^~~~~~~~~~~~~~~~~
beads.cpp: In function 'int main()':
beads.cpp:30:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
beads.cpp:34:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %lld", &a, &b, &c);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 43.0

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