제출 #1086437

#제출 시각아이디문제언어결과실행 시간메모리
1086437User0069구슬과 끈 (APIO14_beads)C++17
0 / 100
2 ms4956 KiB
#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"; } }

컴파일 시 표준 에러 (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);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...