Submission #1086407

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086407		User0069	Beads and wires (APIO14_beads)	C++17	0 / 100	3 ms	4956 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=1e9+7;
int n,dp[maxn][3];
struct edge
{
    int u,v,w;
}e[maxn];
vector<int> adj[maxn];
void dfs(int x,int par)
{
    dp[x][0]=0;
    dp[x][1]=-INF;
    dp[x][2]=-INF;
    int temp[3];
    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++)
        {
            temp[j]=dp[x][j];
        }
        dp[x][0]=temp[0]+max({dp[y][1]+e[i].w,dp[y][0],dp[y][2]});
        dp[x][1]=max(temp[0]+e[i].w+max(dp[y][0],dp[y][2]),temp[1]+max({dp[y][0],dp[y][2],dp[y][1]+e[i].w}));
        dp[x][2]=max(temp[1]+e[i].w+max(dp[y][0],dp[y][2]),temp[2]+max({dp[y][0],dp[y][2],dp[y][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],dp[1][2]);
}

Compilation message (stderr)

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

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