Submission #713086

#	Time	Username	Problem	Language	Result	Execution time	Memory
713086		bin9638	Beads and wires (APIO14_beads)	C++17	0 / 100	4 ms	8148 KiB

beads

#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 (stderr)

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
• Subtask 2: 0 / 15
• Subtask 3: 0 / 29
• Subtask 4: 0 / 43