#include <bits/stdc++.h>
#include "race.h"
//#include "grader.cpp"
#define pii pair<int, int>
#define pb push_back
#define st first
#define nd second
using namespace std;
const int maxN = 2e5 + 10;
const int maxL = 1e6 + 10;
vector<pii> adj[maxN];
int sz[maxN], mx, mn = INT_MAX, k, path[maxL];
bool mark[maxN];
int dfs(int i, int prt=0) {
sz[i] = 1;
for (auto [j, w] : adj[i]) {
if (j == prt || mark[j]) continue;
sz[i] += dfs(j, i);
}
return sz[i];
}
int find_centroid(int i, int n, int prt=0) {
for (auto [j, w] : adj[i]) {
if (j == prt || mark[j]) continue;
if (sz[j] >= n/2) return find_centroid(j, n, i);
}
return i;
}
void dfs2(int i, int prt, bool filling, int dis, int cnt=1) {
if (dis > k) return;
if (filling) path[dis] = min(path[dis], cnt);
else if (path[k-dis] != -1) mn = min(mn, cnt+path[k-dis]);
for (auto [j, w] : adj[i]) {
if (j == prt || mark[j]) continue;
dfs2(j, i, filling, dis+w, cnt+1);
}
}
int decom(int x=0) {
int cen = find_centroid(x, dfs(x));
mark[cen] = 1;
for (auto [j, w] : adj[cen]) {
if (mark[j]) continue;
dfs2(j, cen, 0, w);
dfs2(j, cen, 1, w);
}
for (int i = 1; i < maxL; ++i) path[i] = -1;
for (auto [j, w] : adj[cen]) {
if (!mark[j]) decom(j);
}
}
int best_path(int N, int K, int H[][2], int L[]) {
k = K;
for (int i = 0; i < N-1; ++i) {
adj[H[i][0]].pb({H[i][1], L[i]});
adj[H[i][1]].pb({H[i][0], L[i]});
}
memset(path, -1, sizeof(path));
path[0] = 0;
decom();
return (mn == INT_MAX ? -1 : mn);
}
Compilation message
race.cpp: In function 'int dfs(int, int)':
race.cpp:19:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
19 | for (auto [j, w] : adj[i]) {
| ^
race.cpp: In function 'int find_centroid(int, int, int)':
race.cpp:27:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
27 | for (auto [j, w] : adj[i]) {
| ^
race.cpp: In function 'void dfs2(int, int, bool, int, int)':
race.cpp:38:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
38 | for (auto [j, w] : adj[i]) {
| ^
race.cpp: In function 'int decom(int)':
race.cpp:48:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
48 | for (auto [j, w] : adj[cen]) {
| ^
race.cpp:54:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
54 | for (auto [j, w] : adj[cen]) {
| ^
race.cpp:57:1: warning: no return statement in function returning non-void [-Wreturn-type]
57 | }
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
20 ms |
17904 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
20 ms |
17904 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
20 ms |
17904 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
20 ms |
17904 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |