Submission #992575

#	Time	Username	Problem	Language	Result	Execution time	Memory
992575		star	Beads and wires (APIO14_beads)	C++14	100 / 100	87 ms	23240 KiB

beads

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define starburst ios::sync_with_stdio(0), cin.tie(0)
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define all(x) x.begin(),x.end()
#define inf 0x3f3f3f3f
#define N 200005
int n, a, b, c, ans=0;
vector<pii> adj[N];
int in[N], ex[N];
int pw[N];
void dfs(int v, int parent){
    int sum=0;
    for (int i=0;i<adj[v].size();i++){
        int u=adj[v][i].F;
        if (u==parent){
            pw[v]=adj[v][i].S;
            swap(adj[v][i],adj[v].back());
            adj[v].pop_back();
            i--;
            continue;
        }
        dfs(u,v);
        sum+=in[u];
    }
    in[v]=ex[v]=sum;
    for (auto it:adj[v]){
        int u=it.F;
        if (u==parent) continue;
        in[v]=max(in[v], sum-in[u]+ex[u]+pw[v]+it.S);
    }
}
void dfs2(int v, int parent, int to){
    int sum=parent;
    int mx=to-parent+pw[v];
    int mxx=-inf;
    for (auto it:adj[v]){
        int u=it.F;
        if (u==parent) continue;
        sum+=in[u];
        int now=ex[u]-in[u]+it.S;
        if (mx<now){
            mxx=mx;
            mx=now;
        }
        else if (mxx<now) mxx=now;
    }
    ans=max(ans, sum);
    for (auto it:adj[v]){
        int u=it.F;
        if (u==parent) continue;
        int now=mx;
        if (now==ex[u]-in[u]+it.S) now=mxx;
        dfs2(u, max(sum-in[u], now+sum-in[u]+it.S), sum-in[u]);
    }
}
signed main(){
    starburst;
    cin >> n;
    for (int i=0;i<n-1;i++){
        cin >> a >> b >> c;
        adj[a].pb({b,c});
        adj[b].pb({a,c});
    }
    pw[1]=-inf;
    dfs(1,0);
    dfs2(1,0,0);
    cout << ans;
    return 0;
}

Compilation message (stderr)

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

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