Submission #1110837

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110837		simona1230	Beads and wires (APIO14_beads)	C++17	28 / 100	1069 ms	6992 KiB

beads

#include <bits/stdc++.h>

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

int dp[200001][2];

void dfs(int i,int p)
{
    dp[i][0]=0;
    int minn=1e9;
    for(int j=0;j<v[i].size();j++)
    {
        int nb=v[i][j].first;
        int 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]=-1e9;
    //cout<<i<<" "<<dp[i][0]<<" "<<dp[i][1]<<endl;
}

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

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(int, int)':
beads.cpp:24:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int j=0;j<v[i].size();j++)
      |                 ~^~~~~~~~~~~~

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