oj.uz

Submission #713086

# Submission time Handle Problem Language Result Execution time Memory
713086 2023-03-21T03:34:25 Z bin9638 Beads and wires (APIO14_beads) C++17
0 / 100
 4 ms 8148 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define N 200010
#define ii pair<int,int>
#define fs first
#define sc second
#define ld double
#define int ll

int l[N],r[N],dp[N][2],n;
vector<ii>g[N];
ii f[N];

void selfmax(int&u,int v)
{
    u=max(u,v);
}

int get(int l,int r)
{
    int res=0;
    for(int i=l;i<r;i+=2)
        if(f[i].fs+f[i+1].fs>0)
            res+=f[i].fs+f[i+1].fs;
                else return res;
    return res;
}

void DFS(int u,int p)
{
    dp[u][0]=0;
    for(auto v:g[u])
        if(v.sc!=p)
            DFS(v.sc,u);
    //dp[u][0]
    int dem=0;
    for(int i=0;i<g[u].size();i++)
    {
        ii v=g[u][i];
        if(v.sc!=p)
        {
            dp[u][0]+=max(dp[v.sc][0],dp[v.sc][1]+v.fs);
            f[++dem]={dp[v.sc][0]+v.fs-max(dp[v.sc][0],dp[v.sc][1]+v.fs),i};
        }
    }
    int sum=dp[u][0];
    sort(f+1,f+1+dem,greater<ii>());
    for(int i=1;i<dem;i+=2)
    {
        if(f[i].fs+f[i+1].fs>0)
            dp[u][0]+=f[i].fs+f[i+1].fs;
    }
    //dp[u][1]
    for(int i=1;i<=dem;i++)
    {
        ii v=g[u][f[i].sc];
        int val=dp[v.sc][0]+v.fs+sum-max(dp[v.sc][0],dp[v.sc][1]+v.fs);
        if(i>2)
            val+=get(1,(i-1)-(i-1)%2);
        if(i>1&&i<n&&(i-1)%2==1&&f[i-1].fs+f[i+1].fs>0)
        {
            val+=f[i-1].fs+f[i+1].fs;
            val+=get(i+2,n);
        }else
        {
            val+=get(i+1,n);
        }
        selfmax(dp[u][1],val);
    }
}

int32_t main()
{
    #ifdef SKY
    freopen("A.inp","r",stdin);
    freopen("A.out","w",stdout);
    #endif // SKY
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    memset(dp,-0x3f3f,sizeof(dp));
    cin>>n;
    for(int i=1;i<n;i++)
    {
        int u,v,L;
        cin>>u>>v>>L;
        g[u].pb({L,v});
        g[v].pb({L,u});
    }
    //cout<<sum<<endl;
    DFS(1,0);
    cout<<dp[1][0];
    return 0;
}

Compilation message

beads.cpp: In function 'void DFS(long long int, long long int)':
beads.cpp:41:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for(int i=0;i<g[u].size();i++)
      |                 ~^~~~~~~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 8148 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 8148 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 8148 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 8148 KB Output isn't correct
2 Halted 0 ms 0 KB -