oj.uz

Submission #754143

# Submission time Handle Problem Language Result Execution time Memory
754143 2023-06-07T02:12:05 Z bgnbvnbv Beads and wires (APIO14_beads) C++14
0 / 100
 4 ms 5028 KB 
#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<ll,ll>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=2e5+10;
const ll inf=1e18;
const ll mod=1e9+7;
ll dp[maxN][2];
vector<pli>g[maxN];
ll w[maxN];
void dfs(ll u,ll p)
{
    dp[u][0]=0;
    dp[u][1]=-inf;
    vector<pli>vec;
    for(auto zz:g[u])
    {
        if(zz.fi==p) continue;
        w[zz.fi]=zz.se;
        dfs(zz.fi,u);
        dp[u][0]+=max(dp[zz.fi][0],dp[zz.fi][1]);
        vec.pb({-max(dp[zz.fi][0],dp[zz.fi][1])+dp[zz.fi][0]+zz.se,0});
    }
    sort(vec.begin(),vec.end(),greater<pli>());
    ll x=dp[u][0];
    if(vec.size()>=2)
    {
        dp[u][0]=max(dp[u][0],x+vec[0].fi+vec[1].fi);
    }
    if(vec.size()>=1) dp[u][1]=max(dp[u][1],x+vec[0].fi+w[u]);
    vec.clear();
}
ll u,v,c,n;
void solve()
{
    cin >> n;
    for(int i=1;i<n;i++)
    {
        cin >>u >> v >> c;
        g[u].pb({v,c});
        g[v].pb({u,c});
    }
    dfs(1,0);
    cout <<dp[1][0];
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Subtask #1
0 / 13.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 43.0

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