제출 #383381

#제출 시각아이디문제언어결과실행 시간메모리
383381Saynaa구슬과 끈 (APIO14_beads)C++14
100 / 100
282 ms25700 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 2e5 + 10; int n, tmpp[MAXN], dp[MAXN][4]; int mx1[MAXN], mx2[MAXN], DP[MAXN]; vector< pair< int, int> > adj[MAXN]; int ans; void dfs(int u, int p = -1){ mx1[u] = mx2[u] = -INT_MAX/2; for(int i = 0; i < adj[u].size(); i ++){ int v = adj[u][i].first, w = adj[u][i].second; if( v == p) continue; dfs(v, u); dp[v][1] += w; dp[v][2] = max(dp[v][1], dp[v][0]); DP[u] += dp[v][2]; dp[u][0] += dp[v][2]; int tmp = dp[v][0] - dp[v][2] + w; if( tmp > mx1[u]) mx2[u] = mx1[u], mx1[u] = tmp; else if(tmp > mx2[u]) mx2[u] = tmp; } dp[u][1] = -INT_MAX/2; if( mx1[u] > -INT_MAX/2 ) dp[u][1] = dp[u][0] + mx1[u]; } void dfs2(int u, int p = -1){ if( tmpp[u] > mx1[u]) mx2[u] = mx1[u], mx1[u] = tmpp[u]; else if(tmpp[u] > mx2[u]) mx2[u] = tmpp[u]; ans = max(ans, DP[u]); for(int i= 0; i < adj[u].size(); i ++){ int v = adj[u][i].first; if( v == p) continue; int w = adj[u][i].second; int idk = DP[u] - dp[v][2]; int idk2 = dp[v][0] - dp[v][2] + w; if( idk2 == mx1[u]) idk2 = mx2[u]; else idk2 = mx1[u]; int x = idk; if( idk2 != -INT_MAX/2) x = max(x, idk + idk2 + w); DP[v] += x; tmpp[v] = idk + w - x; dfs2(v, u); } } int main(){ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin >> n; for(int i = 1; i < n; i ++){ int a, b, w; cin >> a >> b >> w, a --, b --; adj[a].push_back({b, w}), adj[b].push_back({a, w}); } dfs(0); tmpp[0] = -INT_MAX/2; dfs2(0, 0); cout << ans << endl; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

beads.cpp: In function 'void dfs(int, int)':
beads.cpp:13:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |  for(int i = 0; i < adj[u].size(); i ++){
      |                 ~~^~~~~~~~~~~~~~~
beads.cpp: In function 'void dfs2(int, int)':
beads.cpp:35: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]
   35 |  for(int i= 0; i < adj[u].size(); i ++){
      |                ~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...