| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 718703 | lam | 도로 폐쇄 (APIO21_roads) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "roads.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e5 + 10;
typedef pair<int,int> ii;
#define ff first
#define ss second
int n,k;
ll dp[2][maxn];
vector <ii> adj[maxn];
priority_queue<ll,vector<ll>,greater<ll>> pq;
void dfs(int x, int p)
{
ll sum = 0LL;
vector <ll> tmp;
for (ii i:adj[x])
if (i.ff!=p)
{
dfs(i.ff,x);
sum += dp[0][i.ff];
tmp.push_back(dp[1][i.ff]+i.ss-dp[0][i.ff]);
}
sort(tmp.begin(),tmp.end(),greater<ll>());
vector <ll> tmp2 = tmp;
dp[0][x] = sum;
while (!tmp.empty()&&(tmp.size()>k||(tmp.back() < 0)))
{
dp[0][x] += tmp.back();
tmp.pop_back();
}
dp[1][x] = sum;
while (!tmp2.empty()&&(tmp2.size()>k+1||(tmp2.back()<0)))
{
dp[1][x] += tmp2.back();
tmp2.pop_back();
}
}
vector <ll> minimum_closure_costs(int N, int vector <int>U, vector<int>V, vector<int>W)
{
n=N;
for (int i=0; i<n; i++) adj[i].clear();
for (int i=0; i<n-1; i++)
{
int u=U[i]; int v=V[i];
int w=W[i];
pq.push(w);
}
vector <ll> ans;
ll num = 0LL;
for (int k=n-1; k>=0; k--)
{
while (pq.size() > k)
{
num+=pq.top(); pq.pop();
}
ans.push_back(num);
}
reverse(ans.begin(),ans.end());
return ans;
}