Submission #1110534

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110534		simona1230	Beads and wires (APIO14_beads)	C++17	28 / 100	1051 ms	6736 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];

void dfs(long long i,long long p)
{
    dp[i][0]=0;
    long long minn=1e18;
    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);
        dp[i][0]+=max(dp[nb][0],dp[nb][1]+dist);
        minn=min(minn,max(dp[nb][0],dp[nb][1]+dist)-dp[nb][0]-dist);
    }

    dp[i][1]=dp[i][0]-minn;
    if(v[i].size()==1)dp[i][1]=-1e18;
    //cout<<i<<" "<<dp[i][0]<<" "<<dp[i][1]<<endl;
}

void solve()
{
    long long ans=0;
    for(long long i=1;i<=n;i++)
    {
        //cout<<"! "<<i<<endl;
        dfs(i,-1);
        ans=max(ans,dp[i][0]);
    }
    cout<<ans<<endl;
}

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

Compilation message (stderr)

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

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