oj.uz

Submission #158433

# Submission time Handle Problem Language Result Execution time Memory
158433 2019-10-17T04:14:00 Z mhy908 Beads and wires (APIO14_beads) C++14
0 / 100
 7 ms 4984 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], 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]+dp2[link[num][i].F]+link[num][i].S);
    }
    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(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:29:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
beads.cpp:33: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 4984 KB Output is correct
2 Correct 6 ms 4984 KB Output is correct
3 Incorrect 7 ms 4984 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 43.0

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