제출 #736363

#제출 시각아이디문제언어결과실행 시간메모리
736363hoainiem도로 폐쇄 (APIO21_roads)C++14
36 / 100
551 ms66140 KiB
#include "roads.h" #include <bits/stdc++.h> #define fi first #define se second #define nmax 100008 const long long inf = 1e18; using namespace std; typedef pair<long long, long long> pii; long long n, sub1 = true, sub2 = true; long long dp[2008][2008][2]; long long f[5][nmax][2]; vector<pii> l[nmax]; long long sdq(int id, int x, int pre, int kt){ if (f[id][x][kt] != -1) return f[id][x][kt]; if (!id && kt) return f[id][x][kt] = inf; long long res = 0; vector<long long>vt; for (pii it : l[x]) if (it.fi != pre){ res += sdq(id, it.fi, x, 1); vt.push_back(sdq(id, it.fi, x, 0) + it.se - sdq(id, it.fi, x, 1)); } sort(vt.begin(), vt.end(), greater<long long>()); while (!vt.empty() && ((int)vt.size() + kt > id || vt.back() < 0)){ res += vt.back(); vt.pop_back(); } return f[id][x][kt] = res; } long long dq(int id, int x, int pre, int kt){ if (dp[id][x][kt] != -1) return dp[id][x][kt]; if (!id && kt) return dp[id][x][kt] = inf; long long res = 0; vector<long long>vt; for (pii it : l[x]) if (it.fi != pre){ res += dq(id, it.fi, x, 1); vt.push_back(dq(id, it.fi, x, 0) + it.se - dq(id, it.fi, x, 1)); } sort(vt.begin(), vt.end(), greater<long long>()); while (!vt.empty() && ((int)vt.size() + kt > id || vt.back() < 0)){ res += vt.back(); vt.pop_back(); } return dp[id][x][kt] = res; } std::vector<long long> minimum_closure_costs(int N, std::vector<int> U, std::vector<int> V, std::vector<int> W) { n = N; for (long long i = 0; i < n - 1; i++){ if (U[i] != 0) sub1 = false; if (U[i] != i || V[i] != i + 1) sub2 = false; l[U[i]].push_back({V[i], W[i]}); l[V[i]].push_back({U[i], W[i]}); } vector<long long>res; if (sub1){ sort(W.begin(), W.end(), greater<int>()); long long j = 0; for (int tmp : W) j += tmp; res.push_back(j); for (long long i = 0; i < n - 1; i++){ j -= W[i]; res.push_back(j); } return res; } if (sub2){ memset(f, -1, sizeof(f)); for (long long k = 0; k < n; k++) if (k < 2) res.push_back(sdq(k, 0, 0, 0)); else res.push_back(0); return res; } assert(n <= 2000); memset(dp, -1, sizeof(dp)); for (long long k = 0; k < n; k++) res.push_back(dq(k, 0, 0, 0)); return res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...