| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1101486 | VinhLuu | 도로 폐쇄 (APIO21_roads) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define int long long
#define all(vin) vin.begin(), vin.end()
using namespace std;
typedef pair<int,int> pii;
const int N = 2e5 + 2;
int n, A[N], B[N], C[N], kq[N], g[N], d[N], T[N], deg[N];
multiset<int> st[N];
vector<pair<int,int>> p[N];
vector<int> vr;
int f[2][N];
void add(int u,int w,int type){
g[u] += type * w;
if(type == 1){
st[u].insert(w);
}else{
auto fin = st[u].find(w);
st[u].erase(fin);
}
}
void dfs(int u){
vector<int> tmp, undo;
int k = T[u], de = deg[u] - k, sum = 0;
while((int)st[u].size() > max(0ll, de)) add(u, (*st[u].rbegin()), -1);
for(auto [j, w] : p[u]) if(T[j] != k){
if(deg[j] <= k) break;
T[j] = k;
dfs(j);
if(f[0][j] + w <= f[1][j]){
sum += f[0][j] + w;
de--;
}else{
sum += f[1][j];
tmp.push_back(f[0][j] + w - f[1][j]);
add(u, f[0][j] + w - f[1][j], 1);
}
}
while((int)st[u].size() > max(0ll, de)){
int val = (*st[u].rbegin());
undo.push_back(val);
add(u, val, -1);
}
f[1][u] = sum + g[u];
while((int)st[u].size() > max(0ll, de - 1)){
int val = (*st[u].rbegin());
undo.push_back(val);
add(u, val, -1);
}
f[0][u] = sum + g[u];
for(auto j : undo) add(u, j, 1);
for(auto j : tmp) add(u, j, -1);
}
vector<int> ver[N];
vector<int> minimum_closure_costs(int _n, vector<int> _u, vector<int> _v, vector<int> _c){
n = _n;
for(int i = 1; i < n; i ++){
int u = _u[i - 1] + 1;
int v = _v[i - 1] + 1;
int c = _c[i - 1];
A[i] = u;
B[i] = v;
C[i] = c;
kq[0] += c;
deg[u]++;
deg[v]++;
p[u].push_back({v, c});
p[v].push_back({u, c});
}
int _max = 0;
vector<int> e;
for(int i = 1; i <= n; i ++){
ver[deg[i]].push_back(i);
e.push_back(i);
}
for(int i = 1; i <= n; i ++) sort(all(p[i]), [&](pii x, pii y){return deg[x.first] > deg[y.first];});
sort(all(e), [&](int x,int y){return deg[x] < deg[y];});
int ptr = 0;
for(int k = 1; k < n; k ++){
while(ptr < e.size() && deg[e[ptr]] == k){
int pos = e[ptr];
for(auto [j, w] : p[pos]) if(deg[j] > k) add(j, w, 1);
ptr++;
}
int ans = 0;
for(int i = ptr; i < (int)e.size(); i ++) if(T[e[i]] != k){
T[e[i]] = k;
dfs(e[i]);
ans += f[1][e[i]];
}
kq[k] = ans;
}
vector<int> _return;
for(int i = 0; i < n; i ++) _return.push_back(kq[i]);
return _return;
}