제출 #1011962

#제출 시각아이디문제언어결과실행 시간메모리
1011962andrei_iorgulescu구슬과 끈 (APIO14_beads)C++14
100 / 100
174 ms80936 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][2]; /** Conditii: - muchiile albastre sa fie de forma 2k - pot alege k noduri si sa dau fiecaruia doua muchii albastre din set, pe care le voi orienta spre nodul respectiv - sa nu existe doua noduri din cele k, astfel incat fiecare muchie din cele 4 orientate spre vreun nod din astea "se uita" si spre celalalt Deci am un dp[nod][0/1][0/1] care reprezinta: suma costurilor max cu care pot face subarb lui nod, folosesc sau nu muchia nod--t[nod], am sau nu am vreun nod albastru in subarbore pentru care ambele muchii care se uita spre el sa ii vina din fii? **/ 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); } } } /* 10 4 10 2 1 2 21 1 3 13 6 7 1 7 9 5 2 4 3 2 5 8 1 6 55 6 8 34 */ void solve(int nod) { if (f[nod].empty()) { dp[nod][0][0] = 0; dp[nod][0][1] = dp[nod][1][0] = dp[nod][1][1] = -inf; return; } for (auto vecin : f[nod]) solve(vecin.first); for (int j = 0; j < 2; j++) for (int q = 0; q < 2; q++) dp[nod][j][q] = -inf; dp[nod][0][0] = 0; for (auto vecin : f[nod]) dp[nod][0][0] += max(dp[vecin.first][0][0],dp[vecin.first][1][0]); 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][0],dp[fiu][1][0]); d[i][1] = dp[fiu][0][0] + cost; } else { d[i][0] = d[i - 1][0] + max(dp[fiu][0][0],dp[fiu][1][0]); d[i][1] = max(d[i - 1][1] + max(dp[fiu][0][0],dp[fiu][1][0]),d[i - 1][0] + dp[fiu][0][0] + cost); } } dp[nod][1][0] = d[f[nod].size() - 1][1] + t[nod].second; d.clear(); d.resize(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][0],dp[fiu][1][0]); d[i][1] = max(dp[fiu][0][1],dp[fiu][1][1]); } else { d[i][0] = d[i - 1][0] + max(dp[fiu][0][0],dp[fiu][1][0]); d[i][1] = max(d[i - 1][1] + max(dp[fiu][0][0],dp[fiu][1][0]),d[i - 1][0] + max(dp[fiu][0][1],dp[fiu][1][1])); } } dp[nod][0][1] = d[f[nod].size() - 1][1]; vector<vector<vector<int>>> dd(f[nod].size()); for (int i = 0; i < f[nod].size(); i++) { dd[i].resize(3); for (int j = 0; j < dd[i].size(); j++) dd[i][j].resize(2); } for (int i = 0; i < f[nod].size(); i++) for (int j = 0; j < 3; j++) for (int q = 0; q < 2; q++) dd[i][j][q] = -inf; for (int i = 0; i < f[nod].size(); i++) { int fiu = f[nod][i].first,cost = f[nod][i].second; if (i == 0) { dd[i][0][0] = max(dp[fiu][0][0],dp[fiu][1][0]); dd[i][1][0] = cost + dp[fiu][0][0]; dd[i][1][1] = cost + dp[fiu][0][1]; } else { dd[i][0][0] = dd[i - 1][0][0] + max(dp[fiu][0][0],dp[fiu][1][0]); dd[i][1][0] = max(dd[i - 1][1][0] + max(dp[fiu][0][0],dp[fiu][1][0]),dd[i - 1][0][0] + cost + dp[fiu][0][0]); dd[i][1][1] = max(dd[i - 1][1][1] + max(dp[fiu][0][0],dp[fiu][1][0]),dd[i - 1][0][0] + cost + dp[fiu][0][1]); dd[i][2][0] = max(dd[i - 1][2][0] + max(dp[fiu][0][0],dp[fiu][1][0]),dd[i - 1][1][0] + cost + dp[fiu][0][0]); dd[i][2][1] = max(dd[i - 1][2][1] + max(dp[fiu][0][0],dp[fiu][1][0]),dd[i - 1][1][0] + cost + dp[fiu][0][1]); dd[i][2][1] = max(dd[i][2][1],dd[i - 1][1][1] + cost + dp[fiu][0][0]); } } dp[nod][0][1] = max(dp[nod][0][1],max(dd[f[nod].size() - 1][2][0],dd[f[nod].size() - 1][2][1])); d.clear(); d.resize(f[nod].size()); for (int i = 0; i < f[nod].size(); i++) d[i].resize(2),d[i][0] = d[i][1] = -inf; 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][0],dp[fiu][1][0]); d[i][1] = dp[fiu][0][1] + cost; } else { d[i][0] = d[i - 1][0] + max(dp[fiu][0][0],dp[fiu][1][0]); d[i][1] = max(d[i - 1][1] + max(dp[fiu][0][0],dp[fiu][1][0]),d[i - 1][0] + dp[fiu][0][1] + cost); } } dp[nod][1][1] = d[f[nod].size() - 1][1] + t[nod].second; //cout << nod << ' ' << dp[nod][0][0] << ' ' << dp[nod][0][1] << ' ' << dp[nod][1][0] << ' ' << dp[nod][1][1] << endl; } 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; } dfs(1); solve(1); cout << max(dp[1][0][0],dp[1][0][1]); return 0; }

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

beads.cpp: In function 'void solve(long long int)':
beads.cpp:68: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]
   68 |     for (int i = 0; i < f[nod].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~
beads.cpp:70: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]
   70 |     for (int i = 0; i < f[nod].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~
beads.cpp:88: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]
   88 |     for (int i = 0; i < f[nod].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~
beads.cpp:90: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]
   90 |     for (int i = 0; i < f[nod].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~
beads.cpp:92:35: warning: unused variable 'cost' [-Wunused-variable]
   92 |         int fiu = f[nod][i].first,cost = f[nod][i].second;
      |                                   ^~~~
beads.cpp:106: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]
  106 |     for (int i = 0; i < f[nod].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~
beads.cpp:109:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |         for (int j = 0; j < dd[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~~
beads.cpp:112: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]
  112 |     for (int i = 0; i < f[nod].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~
beads.cpp:116: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]
  116 |     for (int i = 0; i < f[nod].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~
beads.cpp:139: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]
  139 |     for (int i = 0; i < f[nod].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~
beads.cpp:141: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]
  141 |     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...