제출 #736350

#제출 시각아이디문제언어결과실행 시간메모리
736350hoainiem도로 폐쇄 (APIO21_roads)C++14
24 / 100
581 ms66424 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; long long dp[2008][2008][2]; vector<pii> l[nmax]; 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) { assert((n = N) <= 2000); for (long long i = 0; i < n - 1; i++){ l[U[i]].push_back({V[i], W[i]}); l[V[i]].push_back({U[i], W[i]}); } vector<long long>res; 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...