Submission #934781

#	Time	Username	Problem	Language	Result	Execution time	Memory
934781		irmuun	Beads and wires (APIO14_beads)	C++17	57 / 100	1049 ms	30396 KiB

beads

#include<bits/stdc++.h>
 
using namespace std;
 
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()
 
const ll N=2e5+5;
ll dp[2][N];
vector<pair<ll,ll>>adj[N];
vector<ll>ord;
void dfs(ll v,ll par){
    ord.pb(v);
    for(auto [u,w]:adj[v]){
        if(u!=par){
            dp[1][u]=w;
            dfs(u,v);
            ord.pb(v);
            dp[0][v]=max(dp[0][v]+dp[0][u],dp[1][v]+dp[1][u]);
            dp[1][v]+=dp[0][u];
        }
    }
}
void cal(ll root,ll newRoot){
    ll d=0;
    for(auto [i,w]:adj[root]){
        if(i==newRoot){
            d=w;
            break;
        }
    }
    dp[1][root]=d;
    dp[0][root]=0;
    dp[0][newRoot]=0;
    dp[1][newRoot]=0;
    for(auto [i,w]:adj[root]){
        if(i!=newRoot){
            dp[0][root]=max(dp[0][root]+dp[0][i],dp[1][root]+dp[1][i]);
            dp[1][root]+=dp[0][i];
        }
    }
    for(auto [i,w]:adj[newRoot]){
        dp[0][newRoot]=max(dp[0][newRoot]+dp[0][i],dp[1][newRoot]+dp[1][i]);
        dp[1][newRoot]+=dp[0][i];
    }
}
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n;
    cin>>n;
    for(ll i=1;i<n;i++){
        ll u,v,w;
        cin>>u>>v>>w;
        adj[u].pb({v,w});
        adj[v].pb({u,w});
    }
    fill(dp[0],dp[0]+n+1,0);
    fill(dp[1],dp[1]+n+1,0);
    dfs(1,-1);
    ll ans=dp[1][1];
    for(ll r=1;r<ord.size();r++){
        if(ord[r-1]!=ord[r]){
            cal(ord[r-1],ord[r]);
            ans=max(ans,dp[1][ord[r]]);
        }
    }
    cout<<ans;
}

Compilation message (stderr)

beads.cpp: In function 'int main()':
beads.cpp:66:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for(ll r=1;r<ord.size();r++){
      |                ~^~~~~~~~~~~

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