| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 708332 | 600Mihnea | 도로 폐쇄 (APIO21_roads) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "roads.h"
#include <cmath>
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <cassert>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>
#include <numeric>
using namespace std;
typedef long long ll;
#define all(x) x.begin(), x.end()
#define f first
#define s second
#define pb push_back
#define pii pair<int, int>
#define ve vector
#define vei vector<int>
#define vell vector<ll>
#define sz(x) ((int)x.size())
#define each(it, x) for (auto &it : x)
#define debug(x) cout << #x << " = " << x << "\n";
#define FU function
#define VO void
vell minimum_closure_costs(int N, vei U, vei V, vei W) {
int n = N;
assert(sz(U) == n - 1);
assert(sz(V) == n - 1);
assert(sz(W) == n - 1);
#ifdef ONPC
debug(n);
each(it, U) cout << it << " "; cout << "\n";
each(it, V) cout << it << " "; cout << "\n";
each(it, W) cout << it << " "; cout << "\n";
#endif
ve<ve<pii>> g(n);
for (int i = 0; i < n - 1; i++)
g[U[i]].pb({ V[i], W[i] }),
g[V[i]].pb({ U[i], W[i] });
vei ord, deg(n, 0), pap(n, -1), upp(n, 0);
for (int i = 0; i < n; i++) deg[i] = sz(g[i]);
FU<VO(int, int)>build = [&](int a, int par)
{
pap[a] = par;
ve<pii> kids;
ord.pb(a);
each(it, g[a])
{
int b = it.f, c = it.s;
if (b == par) continue;
upp[b] = c;
build(b, a);
kids.pb({ b, c });
}
g[a] = kids;
};
build(0, -1);
reverse(all(ord));
vei loc(n);
for (int i = 0; i < n; i++) loc[ord[i]] = i;
sort(g[i].begin(), g[i].end(), [&](pair<int, int> i, pair<int, int> j) {return deg[i.first] > deg[j.first]; });
vector<vector<int>> devine(n);
for (int i = 0; i < n; i++)
{
devine[deg[i]].pb(i);
}
vell sol(n, 0);
vei verts;
vell dp0(n, 0), dp1(n, 0);
for (int k = n - 1; k >= 0; k--)
{
each(x, devine[k]) verts.pb(x);
sort(all(verts), [&](int a, int b) {return loc[a] < loc[b]; });
// 0 => are gradul <= k + 0
// 1 => are gradul <= k + 1
ll print = 0;
each(a, verts)
{
assert(deg[a] >= k);
each(rem, vei({ k - 1, k }))
{
// sterg muchia => dp1 + cost
// pastrez muchia => dp0
int total = sz(g[a]);
int pastrez = min(total, rem);
ll su = 0;
each(it, g[a]) if (deg[a] >= k) su += dp1[it.first] + it.second;
each(it, g[a]) if (deg[a] < k) su += it.second;
vector<ll> difs;
each(it, g[a]) if (deg[a] >= k) difs.pb(min(0LL, dp0[it.first] - dp1[it.first] - it.second));
each(it, g[a]) if (deg[a] < k) difs.pb(-it.second);
sort(difs.begin(), difs.end());
for (int i = 0; i < pastrez; i++)
{
assert(0 <= i && i < sz(difs));
su += difs[i];
}
if (rem == k - 1) dp0[a] = su; else dp1[a] = su;
}
if (a == 0)
{
print += dp1[a];
}
else
{
if (deg[pap[a]] < k)
{
print += min(dp0[a], dp1[a] + upp[a]);
}
}
assert(dp0[a] >= dp1[a]);
}
sol[k] = print;
}
return sol;
}