Submission #1201846

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201846		Szymon_Pilipczuk	Beads and wires (APIO14_beads)	C++20	100 / 100	133 ms	26508 KiB

beads

#include <bits/stdc++.h>
using namespace std;
int ans[200000][4];
bool vis[200000];
vector<vector<pair<int,int>>> gr;
void dfs(int v)
{
    vis[v] =true;
    int mx = -2e9;
    int mx2 = 0;
    int mx3 = -2e9;
    vector<pair<int,int>> q;
    vector<pair<int,int>> q2;
    int cans = 0;
    for(int i = 0;i<gr[v].size();i++)
    {
        if(!vis[gr[v][i].first])
        {
            dfs(gr[v][i].first);
            ans[v][0] += ans[gr[v][i].first][1];
            ans[v][1] += ans[gr[v][i].first][1];
            mx = max(mx,gr[v][i].second+ans[gr[v][i].first][0]-ans[gr[v][i].first][1]);
            mx2 = max(mx2,ans[gr[v][i].first][3] - ans[gr[v][i].first][1]);
            ans[v][2] += ans[gr[v][i].first][1];
            q.push_back({ans[gr[v][i].first][2]-ans[gr[v][i].first][1]+gr[v][i].second,i});
            q2.push_back({ans[gr[v][i].first][0]-ans[gr[v][i].first][1]+gr[v][i].second,i});
            cans+=ans[gr[v][i].first][1];
            mx3 = max(mx3,ans[gr[v][i].first][2]-ans[gr[v][i].first][1]+gr[v][i].second);
        }
        else
        {
            ans[v][1] += gr[v][i].second;
            ans[v][3] += gr[v][i].second;
        }
    }
    ans[v][1] += mx;
    ans[v][2] += mx2;
    if(q.size() > 1)
    {
        sort(q.begin(),q.end());
        reverse(q.begin(),q.end());
        sort(q2.begin(),q2.end());
        reverse(q2.begin(),q2.end());
        if(q[0].second != q2[0].second)
        {
            ans[v][2] = max(ans[v][2],cans+q[0].first+q2[0].first);
        }
        else
        {
            ans[v][2] = max(ans[v][2],max(cans+q[0].first+q2[1].first,cans+q[1].first+q2[0].first));
        }
    }
    ans[v][3] += mx3+cans;
    ans[v][3] = max(ans[v][3],ans[v][2]);
    ans[v][1] = max(ans[v][1],ans[v][0]);
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cerr.tie(0);
    int n;
    cin>>n;
    gr.resize(n);
    for(int i = 0;i<n-1;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        a--;b--;
        gr[a].push_back({b,c});
        gr[b].push_back({a,c});
    }
    dfs(0);
    cout<<ans[0][2];
}

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