Submission #1086438

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086438		User0069	Beads and wires (APIO14_beads)	C++17	100 / 100	111 ms	38360 KiB

beads

#include<bits/stdc++.h>
#define taskname ""
#define el '\n'
#define fi first
#define sc second
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
#define int long long
using namespace std;
#define Faster ios_base::sync_with_stdio(false);cin.tie(0);
const int maxn=2e5+33;
const int N=1e5;
const int mod=1e9+7;
const long long INF=1e18+2;
int n,dp[maxn][3][2];
struct edge
{
    int u,v,w;
}e[maxn];
vector<int> adj[maxn];
void dfs(int x,int par)
{
    dp[x][0][0]=0;
    dp[x][0][1]=-INF;
    dp[x][1][0]=-INF;
    dp[x][1][1]=-INF;
    dp[x][2][0]=-INF;
    dp[x][2][1]=-INF;
    int temp[3][2];
    for(int i:adj[x])
    {
        int y=e[i].u+e[i].v-x;
        if(y==par) continue;
        dfs(y,x);
        for(int j=0;j<3;j++)
        {
            for(int jj=0;jj<2;jj++)
            temp[j][jj]=dp[x][j][jj];
        }
        dp[x][0][0]=max(temp[0][0]+dp[y][0][0],temp[0][0]+dp[y][1][0]+e[i].w);
        dp[x][0][1]=max({temp[0][1]+dp[y][0][0],temp[0][1]+dp[y][1][0]+e[i].w,temp[0][0]+dp[y][0][1],temp[0][0]+dp[y][1][1]+e[i].w,temp[0][0]+dp[y][2][0],temp[0][0]+dp[y][2][1]});
        dp[x][1][0]=max({temp[1][0]+dp[y][0][0],temp[1][0]+dp[y][1][0]+e[i].w,temp[0][0]+e[i].w+dp[y][0][0]});
        dp[x][1][1]=max({temp[0][0]+e[i].w+dp[y][2][0],temp[0][0]+e[i].w+dp[y][2][1],temp[0][0]+e[i].w+dp[y][0][1],temp[1][1]+dp[y][0][0],temp[1][1]+dp[y][1][0]+e[i].w});
        dp[x][2][0]=max({temp[2][0]+dp[y][0][0],temp[2][0]+dp[y][1][0]+e[i].w,temp[1][0]+e[i].w+dp[y][0][0]});
        dp[x][2][1]=max({temp[2][1]+dp[y][0][0],temp[2][1]+dp[y][1][0]+e[i].w,
            temp[1][1]+dp[y][0][0]+e[i].w,temp[1][0]+e[i].w+dp[y][0][1],temp[1][0]+e[i].w+dp[y][2][0],temp[1][0]+dp[y][2][1]+e[i].w});
    }
}
signed main()
{
    if (fopen(taskname".INP","r"))
    {
        freopen(taskname".INP","r",stdin);
        freopen(taskname".OUT","w",stdout);
    }
    Faster
    cin>>n;
    for(int i=1;i<n;i++)
    {
        cin>>e[i].u>>e[i].v>>e[i].w;
        adj[e[i].u].push_back(i);
        adj[e[i].v].push_back(i);
    }
    dfs(1,0);
    cout<<max({dp[1][0][1],dp[1][2][1],dp[1][0][0],dp[1][2][0]})<<"\n";
//    for(int i=1;i<=n;i++)
//    {
//        for(int j=0;j<=2;j++)
//        {
//            for(int k=0;k<=1;k++)
//            {
//                cout<<dp[i][j][k]<<" ";
//            }
//        }
//        cout<<"\n";
//    }
}

Compilation message (stderr)

beads.cpp: In function 'int main()':
beads.cpp:53:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         freopen(taskname".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
beads.cpp:54:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         freopen(taskname".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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