제출 #938862

#제출 시각아이디문제언어결과실행 시간메모리
938862sysia구슬과 끈 (APIO14_beads)C++17
0 / 100
0 ms348 KiB
//Sylwia Sapkowska #include <bits/stdc++.h> #pragma GCC optimize("O3", "unroll-loops") using namespace std; void __print(int x) {cerr << x;} void __print(long long x) {cerr << x;} void __print(long double x) {cerr << x;} void __print(char x) {cerr << "'" << x << "'";} void __print(const char *x) {cerr << '"' << x << '"';} void __print(const string &x) {cerr << '"' << x << '"';} void __print(bool x) {cerr << (x ? "true" : "false");} template<typename T, typename V> void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';} template<typename T> void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";} void _print() {cerr << "]\n";} template <typename T, typename... V> void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);} #ifdef LOCAL #define debug(x...) cerr << "[" << #x << "] = ["; _print(x) #else #define debug(x...) #endif #define int long long typedef pair<int, int> T; const int oo = 1e18, oo2 = 1e9+7, K = 30; const int mod = 998244353; void solve(){ int n; cin >> n; vector<vector<T>>g(n+1); for (int i = 1; i<n; i++){ int a, b, c; cin >> a >> b >> c; g[a].emplace_back(b, c); g[b].emplace_back(a, c); } vector dp(n+1, vector<int>(2)); function<void(int, int, int)>dfs = [&](int v, int pa, int cc){ int s = 0; array<int, 2>mx = {-oo, -oo}; for (auto [x, c]: g[v]){ if (x == pa) continue; dfs(x, v, c); s += max(dp[x][0], dp[x][1]); int val = dp[x][0] + c - max(dp[x][1], dp[x][0]); debug(v, x, val); for (int rep = 0; rep < 2; rep++) { if (mx[rep] <= val) { swap(mx[rep], val); } } } dp[v][1] = max(0ll, cc + s + mx[0]); dp[v][0] = s+max(0ll, mx[0] + mx[1]); debug(v, dp[v][0], dp[v][1], mx); //dp[v][1] = cc+dp[u][0]+c-dp[u][1]+s1 //dp[v][0] -> musze znalezc dwa o maksymalnym }; dfs(1, 1, 0); cout << dp[1][0] << "\n"; } int32_t main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; //cin >> t; while (t--) solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...