이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
template <class X, class Y>
bool cmin(X &a, const Y &b) {
return a > b ? a = b, 1 : 0;
}
const long long INF = 1e18;
const int MAXN = 200005;
struct Fenwick {
vector <int> cnt; int N, LOG;
vector <long long> sum;
void init(int N) {
this->N = N;
cnt.assign(N + 1, 0);
sum.assign(N + 1, 0);
LOG = __lg(N);
}
void add(int i, int v) {
for (; i <= N; i += i & -i) {
cnt[i]++; sum[i] += v;
}
}
long long get(int k) {
if (k < 0) return 0;
int p = 0; long long ans = 0;
for (int l = 1 << LOG; l > 0; l >>= 1)
if (p + l <= N && k >= cnt[p + l]) {
k -= cnt[p += l]; ans += sum[p];
}
return k > 0 ? INF : ans;
}
};
int par[MAXN], val[MAXN], ord[MAXN];
vector <pair <int, int>> adj[MAXN];
long long DP[MAXN][2];
int prv[MAXN], nxt[MAXN], ptr, lim;
int tin[MAXN], tout[MAXN], ver[MAXN];
Fenwick BIT[MAXN];
void del(int i) {
nxt[prv[i]] = nxt[i];
prv[nxt[i]] = prv[i];
}
void DFS1(int u) {
ver[tin[u] = ++ptr] = u;
int cnt = 0;
for (auto e : adj[u]) {
int v, w; tie(w, v) = e;
if (v != par[u]) {
par[v] = u; val[v] = w;
ord[v] = ++cnt; DFS1(v);
}
}
tout[u] = ptr;
}
void DFS2(int u) {
vector <long long> tmp;
long long sum = 0;
while (nxt[ptr] <= tout[u]) {
ptr = nxt[ptr];
int v = ver[ptr]; DFS2(v);
if (par[v] == u) {
sum += DP[v][0];
tmp.push_back(DP[v][1] - DP[v][0]);
} else sum += min(DP[v][1], DP[v][0]);
}
int can = adj[u].size() - lim;
DP[u][0] = min(INF, sum + BIT[u].get(can));
DP[u][1] = min(INF, sum + BIT[u].get(can - 1));
for (int i = 0; i < tmp.size(); i++) {
sum += tmp[i];
cmin(DP[u][0], sum + BIT[u].get(can - i - 1));
cmin(DP[u][1], sum + BIT[u].get(can - i - 2));
}
if (u) DP[u][1] = DP[u][1] + val[u];
else DP[u][1] = INF;
}
long long compute() {
ptr = 0; long long ans = 0;
if (lim == 1) cerr << nxt[1] << '\n';
while (nxt[ptr] <= tout[0]) {
ptr = nxt[ptr];
int u = ver[ptr]; DFS2(u);
ans += min(DP[u][0], DP[u][1]);
}
return ans;
}
vector <long long> minimum_closure_costs(int N,
vector <int> U, vector <int> V, vector <int> W) {
vector <int> nodes;
for (int i = 0; i < N; i++) {
adj[i].clear();
prv[i + 1] = i; nxt[i + 1] = i + 2;
nodes.push_back(i);
}
prv[N + 1] = N; nxt[0] = 1;
for (int i = 0; i + 1 < N; i++) {
adj[U[i]].emplace_back(W[i], V[i]);
adj[V[i]].emplace_back(W[i], U[i]);
}
for (int i = 0; i < N; i++) {
BIT[i].init(adj[i].size());
sort(adj[i].begin(), adj[i].end());
}
DFS1(ptr = 0);
sort(nodes.begin(), nodes.end(),
[&](int u, int v) {
return adj[u].size() < adj[v].size();
});
vector <long long> costs(N);
for (int i = 0, j = 0; i < N; i++) {
while (j < N && adj[nodes[j]].size() <= i) {
int u = nodes[j++];
if (u && adj[par[u]].size() > i)
BIT[par[u]].add(ord[u], val[u]);
del(tin[u]);
}
lim = i; costs[i] = compute();
}
return costs;
}
컴파일 시 표준 에러 (stderr) 메시지
roads.cpp: In function 'void DFS2(int)':
roads.cpp:81:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
81 | for (int i = 0; i < tmp.size(); i++) {
| ~~^~~~~~~~~~~~
roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:125:46: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
125 | while (j < N && adj[nodes[j]].size() <= i) {
| ~~~~~~~~~~~~~~~~~~~~~^~~~
roads.cpp:127:41: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
127 | if (u && adj[par[u]].size() > i)
| ~~~~~~~~~~~~~~~~~~~^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |