Submission #409006

#	Time	Username	Problem	Language	Result	Execution time	Memory
409006		TLP39	Beads and wires (APIO14_beads)	C++14	0 / 100	4 ms	5004 KiB

beads

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int,int> pii;

int n;
int ans[200010][2];
int par[200010];
int distpar[200010];
vector<pii> adj[200010];

void dfs(int v)
{
    for(int i=0;i<adj[v].size();i++)
    {
        if(par[v]==adj[v][i].first) continue;
        par[adj[v][i].first]=v;
        distpar[adj[v][i].first]=adj[v][i].second;
        dfs(adj[v][i].first);
    }
}

void init()
{
    scanf("%d",&n);
    int a,b,c;
    for(int i=1;i<n;i++)
    {
        scanf("%d %d %d",&a,&b,&c);
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }
    par[1]=0;
    distpar[1]=-1000000;
    dfs(1);
}

void solve(int v)
{
    ans[v][0]=0;
    ans[v][1]=0;
    if(adj[v].size()==1 && v!=1) return;
    if(adj[v].size()-(v!=1)==1)
    {
        int temp=adj[v][0].first;
        if(temp==par[v]) temp=adj[v][1].first;
        ans[v][0]=ans[temp][1];
        if(v!=1) ans[v][1]=max(ans[v][0],distpar[v]+distpar[temp]+ans[temp][0]);
        return;
    }
    int tot=0;
    for(int i=0;i<adj[v].size();i++)
    {
        if(adj[v][i].first==par[v]) continue;
        tot+=ans[adj[v][i].first][1];
    }
    int ma[2]={-1000000,-1000000},hold;
    for(int i=0;i<adj[v].size();i++)
    {
        if(adj[v][i].first==par[v]) continue;
        hold=adj[v][i].second+ans[adj[v][i].first][0]-ans[adj[v][i].first][1];
        if(hold>ma[0])
        {
            ma[1]=ma[0];
            ma[0]=hold;
        }
        else if(hold>ma[1]) ma[1]=hold;
    }
    ans[v][0]=tot+max(0,ma[0]+ma[1]);
    if(v==1) return;
    ans[v][1]=max(ans[v][0],distpar[v]+ma[0]+tot);
    return;
}

void dp_solve()
{
    queue<int> q;
    int deg[n+1];
    for(int i=1;i<=n;i++)
    {
        deg[i]=adj[i].size()-(i!=1);
        if(deg[i]==0) q.push(i);
    }
    int fr;
    while(!q.empty())
    {
        fr=q.front();
        q.pop();
        solve(fr);
        deg[par[fr]]--;
        if(!deg[par[fr]]) q.push(par[fr]);
    }
}

int main()
{
    init();
    dp_solve();
    printf("%d",ans[1][0]);
}

Compilation message (stderr)

beads.cpp: In function 'void dfs(int)':
beads.cpp:14: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]
   14 |     for(int i=0;i<adj[v].size();i++)
      |                 ~^~~~~~~~~~~~~~
beads.cpp: In function 'void solve(int)':
beads.cpp:52: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]
   52 |     for(int i=0;i<adj[v].size();i++)
      |                 ~^~~~~~~~~~~~~~
beads.cpp:58: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]
   58 |     for(int i=0;i<adj[v].size();i++)
      |                 ~^~~~~~~~~~~~~~
beads.cpp: In function 'void init()':
beads.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
beads.cpp:29:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         scanf("%d %d %d",&a,&b,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

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