이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "bits/stdc++.h"
// @JASPER'S BOILERPLATE
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
#define REP(i, b) for(int i = 0; i < b; i++)
#define PER(i, b) for(int i = b - 1; i >= 0; i--)
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#ifdef JASPER2
#include "debug.h"
#else
#define debug(...) 166
#endif
//#define int long long
using pii = pair < int, int >;
const ll LINF = 1e18 + 5;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const int MAX = 2e5 + 5;
int n, k;
vector <pii> adj[MAX];
int cnt[MAX * 5];
int sz[MAX];
bool vis[MAX];
int Tsize = 0;
void reSubsize(int u, int p) {
sz[u] = 1;
for (auto &[w, v] : adj[u]) {
if (v != p && !vis[v]) {
reSubsize(v, u);
sz[u] += sz[v];
}
}
}
int getCentroid(int u, int p) {
for (auto &[w, v] : adj[u])
if (v != p && !vis[v] && sz[v] > Tsize / 2)
return getCentroid(v, u);
return u;
}
int f[MAX * 5];
// f(i) : Minimum edge to form i length from subtree to current centroid (0 in sub;
int maxW, ans;
int nCur;
vector <pii> subtree;
void process(int u, int p, int eCnt, int W) {
if (W > k)
return;
if (k >= W && cnt[k - W] == nCur)
ans = min(ans, eCnt + f[k - W]);
subtree.push_back({eCnt, W});
for (auto &[w, v] : adj[u]) {
if (v != p && !vis[v]) {
process(v, u, eCnt + 1, W + w);
}
}
}
void decompose(int u, int p) {
reSubsize(u, 0);
Tsize = sz[u];
int x = getCentroid(u, 0);
++nCur;
cnt[0] = nCur;
debug(nCur);
f[0] = 0;
vis[x] = 1;
vector <pii> valid;
for (auto [w, v] : adj[x]) {
subtree.clear();
if (!vis[v]) {
process(v, x, 1, w);
valid.push_back({w, v});
}
for (auto [eCnt, W] : subtree) {
if (cnt[W] != nCur || (cnt[W] == nCur && f[W] > eCnt)) {
cnt[W] = nCur;
f[W] = eCnt;
}
}
}
for (auto [w, v] : valid) {
decompose(v, x);
}
}
int N, K;
int H[MAX][2];
int L[MAX];
int best_path(int N, int K, int a[][2], int W[]) {
cin >> n >> k;
n = N, k = K;
for (int i = 0; i < n; ++i) {
int u = a[i][0], v = a[i][1], w = W[i];
++u, ++v;
adj[u].push_back({w, v});
adj[v].push_back({w, u});
maxW += w;
}
maxW = min(k, maxW);
ans = INF;
for (int i = 0; i <= k; ++i) f[i] = INF;
decompose(1, 0);
if (ans == INF) ans = -1;
cout << ans << "\n";
}
컴파일 시 표준 에러 (stderr) 메시지
race.cpp: In function 'void decompose(int, int)':
race.cpp:16:20: warning: statement has no effect [-Wunused-value]
16 | #define debug(...) 166
| ^~~
race.cpp:76:5: note: in expansion of macro 'debug'
76 | debug(nCur);
| ^~~~~
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:120:1: warning: no return statement in function returning non-void [-Wreturn-type]
120 | }
| ^
# | 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... |