Submission #1111157

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111157		simona1230	Beads and wires (APIO14_beads)	C++17	100 / 100	124 ms	35900 KiB

beads

#include <bits/stdc++.h>

using namespace std;

long long n;
vector<pair<long long,long long> > v[200001];
void read()
{
    cin>>n;
    for(long long i=1;i<n;i++)
    {
        long long x,y,z;
        cin>>x>>y>>z;
        v[x].push_back({y,z});
        v[y].push_back({x,z});
    }
}

long long dp[200001][2],up[200001][2];
long long min1[200001],min2[200001];
long long ver1[200001],ver2[200001];
long long ans;

void dfs(long long i,long long p)
{
    min1[i]=1e9;
    min2[i]=1e9;
    for(long long j=0;j<v[i].size();j++)
    {
        long long nb=v[i][j].first;
        long long dist=v[i][j].second;

        if(nb==p)continue;

        dfs(nb,i);

        long long h=max(dp[nb][0],dp[nb][1]+dist);
        dp[i][0]+=h;

        long long curr=h-dp[nb][0]-dist;
        if(min1[i]>curr)min2[i]=min1[i],min1[i]=curr,ver2[i]=ver1[i],ver1[i]=nb;
        else if(min2[i]>curr)min2[i]=curr,ver2[i]=nb;
    }

    dp[i][1]=dp[i][0]-min1[i];
    if(v[i].size()==1)dp[i][1]=-1e18;
}

void calc(long long i,long long p)
{
    for(long long j=0;j<v[i].size();j++)
    {
        long long nb=v[i][j].first;
        long long d=v[i][j].second;

        if(nb==p)continue;

        long long h=max(dp[nb][0],dp[nb][1]+d);

        long long i0=dp[i][0]+up[i][0]-h;

        long long t1=dp[i][1]+up[i][0]-h;
        if(ver1[i]==nb)
        {
            t1+=min1[i];
            t1-=min2[i];
            if(ver2[i]==0)t1=-1e9;
        }
        long long t2=dp[i][0]+up[i][1]-h;
        if(i==1)t2=-1e9;

        long long i1=max(t1,t2);

        up[nb][0]=max(i0,i1+d);
        up[nb][1]=i0+d;
        //cout<<nb<<" "<<i<<" "<<ver1[i]<<" "<<dp[i][1]<<" "<<i0<<" "<<i1<<" "<<up[nb][0]<<" "<<up[nb][1]<<endl;

        ans=max(ans,up[nb][0]+dp[nb][0]);

        calc(nb,i);
    }
}

void solve()
{
    dfs(1,0);
    ans=dp[1][0];
    //cout<<ans<<endl;
    calc(1,0);
    cout<<ans<<endl;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	read();
	solve();
	return 0;
}
/*
10
1 2 7
1 3 1
3 10 14
1 4 5
2 5 2
2 6 3
4 7 4
4 8 2
4 9 3

5
1 2 1
2 3 2
3 4 4
4 5 3
5 6 9
6 7 1
7 8 3
*/

Compilation message (stderr)

beads.cpp: In function 'void dfs(long long int, long long int)':
beads.cpp:28:24: 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]
   28 |     for(long long j=0;j<v[i].size();j++)
      |                       ~^~~~~~~~~~~~
beads.cpp: In function 'void calc(long long int, long long int)':
beads.cpp:51:24: 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]
   51 |     for(long long j=0;j<v[i].size();j++)
      |                       ~^~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 15 / 15
• Subtask 3: 29 / 29
• Subtask 4: 43 / 43