제출 #1011873

#제출 시각아이디문제언어결과실행 시간메모리
1011873andrei_iorgulescu구슬과 끈 (APIO14_beads)C++14
0 / 100
4 ms9820 KiB
#include <bits/stdc++.h> using namespace std; #define int long long int inf = 2e9; int root; int n; vector<pair<int,int>> g[200005], f[200005]; pair<int,int> t[200005]; int dp[200005][2]; void dfs(int nod) { for (auto vecin : g[nod]) { if (vecin.first != t[nod].first) { f[nod].push_back(vecin); t[vecin.first] = {nod,vecin.second}; dfs(vecin.first); } } } void calc_dp0(int nod) { vector<vector<int>> d(f[nod].size()); for (int i = 0; i < f[nod].size(); i++) d[i].resize(3); for (int i = 0; i < f[nod].size(); i++) { int fiu = f[nod][i].first,cost = f[nod][i].second; if (i == 0) { d[i][2] = -inf; d[i][0] = max(dp[fiu][0],dp[fiu][1]); d[i][1] = dp[fiu][0] + cost; } else { d[i][0] = d[i - 1][0] + max(dp[fiu][0],dp[fiu][1]); d[i][1] = max(d[i - 1][0] + dp[fiu][0] + cost,d[i - 1][1] + max(dp[fiu][0],dp[fiu][1])); d[i][2] = max(d[i - 1][1] + dp[fiu][0] + cost,d[i - 1][2] + max(dp[fiu][0],dp[fiu][1])); } } dp[nod][0] = max(d[f[nod].size() - 1][0],d[f[nod].size() - 1][2]); } void calc_dp1(int nod) { vector<vector<int>> d(f[nod].size()); for (int i = 0; i < f[nod].size(); i++) d[i].resize(2); for (int i = 0; i < f[nod].size(); i++) { int fiu = f[nod][i].first,cost = f[nod][i].second; if (i == 0) { d[i][0] = max(dp[fiu][0],dp[fiu][1]); d[i][1] = dp[fiu][0] + cost; } else { d[i][0] = d[i - 1][0] + max(dp[fiu][0],dp[fiu][1]); d[i][1] = max(d[i - 1][0] + dp[fiu][0] + cost,d[i - 1][1] + max(dp[fiu][0],dp[fiu][1])); } } dp[nod][1] = d[f[nod].size() - 1][1] + t[nod].second; } /* 5 1 2 1 2 3 1 3 4 1 4 5 1 */ void solve(int nod) { for (auto vecin : f[nod]) solve(vecin.first); if (f[nod].size() == 0) { dp[nod][0] = 0; dp[nod][1] = -inf; return; } calc_dp0(nod); if (nod != root) calc_dp1(nod); } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n; for (int i = 1; i < n; i++) { int x,y,z; cin >> x >> y >> z; g[x].push_back({y,z}); g[y].push_back({x,z}); } if (n == 2) { cout << 0; return 0; } for (int i = 1; i <= n; i++) if (g[i].size() == 1) root = i; dfs(root); solve(root); cout << dp[root][0]; return 0; }

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

beads.cpp: In function 'void calc_dp0(long long int)':
beads.cpp:31:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for (int i = 0; i < f[nod].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~
beads.cpp:33:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for (int i = 0; i < f[nod].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~
beads.cpp: In function 'void calc_dp1(long long int)':
beads.cpp:55:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for (int i = 0; i < f[nod].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~
beads.cpp:57:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for (int i = 0; i < f[nod].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...