이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std ;
template<class X, class Y>
bool minimize(X &x, const Y &y) {
if(x > y) return x = y, true ;
return false ;
}
const int inf = 1e9 ;
const int lim = 1e6 + 5 ;
struct E {
int u, v, w ;
E() {}
E(int a, int b, int c): u(a), v(b), w(c) {}
};
int g[lim], child[lim], n, k, res = inf ;
vector<int> adj[lim] ;
bitset<lim> del ;
E e[lim] ;
int other(int i, int u) {
return e[i].u ^ e[i].v ^ u ;
}
void dfs(int u, int par) {
child[u] = 1 ;
for(int i : adj[u]) {
int v = other(i, u) ;
if(!del[v] && v != par) {
dfs(v, u) ;
child[u] += child[v] ;
}
}
}
int find_centroid(int u, int par, int cur) {
for(int i : adj[u]) {
int v = other(i, u) ;
if(!del[v] && v != par && child[v] > (cur >> 1)) {
return find_centroid(v, u, cur) ;
}
}
return u ;
}
void dfs_calc(int u, int par, int h, int len) {
if(len > k) return ;
minimize(res, h + g[k - len]) ;
for(int i : adj[u]) {
int v = other(i, u) ;
if(!del[v] && v != par) {
dfs_calc(v, u, h + 1, len + e[i].w) ;
}
}
}
void dfs_up(int u, int par, int h, int len, vector<int> &tmp) {
if(len > k) return ;
tmp.push_back(len) ;
minimize(g[len], h) ;
for(int i : adj[u]) {
int v = other(i, u) ;
if(!del[v] && v != par) {
dfs_up(v, u, h + 1, len + e[i].w, tmp) ;
}
}
}
void decomp(int root) {
// cerr << root << ' ' ;
dfs(root, 0) ;
root = find_centroid(root, 0, child[root]) ;
vector<int> tmp ;
for(int i : adj[root]) {
int v = other(i, root) ;
if(!del[v]) {
dfs_calc(v, root, 1, e[i].w) ;
dfs_up(v, root, 1, e[i].w, tmp) ;
}
}
del.set(root) ;
for(int k : tmp) {
g[k] = inf ;
}
for(int i : adj[root]) {
int v = other(i, root) ;
if(!del[v]) {
decomp(v) ;
}
}
}
int best_path(int N, int K, int H[][2], int L[]) {
n = N ; k = K ;
for(int i = 0; i < n - 1; i ++) {
int u = H[i][0] + 1, v = H[i][1] + 1 ;
e[i] = E(u, v, L[i]) ;
adj[u].push_back(i) ;
adj[v].push_back(i) ;
}
for(int i = 1; i <= lim; i ++) {
g[i] = inf ;
}
decomp(1) ;
return res == inf ? -1 : res ;
}
컴파일 시 표준 에러 (stderr) 메시지
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:107:14: warning: iteration 1000004 invokes undefined behavior [-Waggressive-loop-optimizations]
107 | g[i] = inf ;
| ~~~~~^~~~~
race.cpp:106:22: note: within this loop
106 | for(int i = 1; i <= lim; 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... |