#include "bits/stdc++.h"
#include "race.h"
using namespace std;
void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
return o >> a.first >> a.second;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
bool is = false;
for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
return o << '}';
}
#ifdef local
#define test(args...) abc("[" + string(#args) + "]", args)
#else
#define test(args...) void(0)
#endif
using ll = long long;
vector<pair<int, int>> adj[200005];
int l[200005];
int seen[200005];
int sz[200005];
int timer = 1;
int idx[200005];
int cnt[200005];
int n, k;
int ans;
int find_centroid(int node, int par, int n) {
for (auto a : adj[node]) {
if (a.first == par) continue;
if (!seen[a.first] && sz[a.first] >= n / 2) return find_centroid(a.first, node, n);
}
return node;
}
int find_size(int node, int par = -1) {
if (seen[node]) return 0;
sz[node] = 1;
for (auto a : adj[node]) {
if (a.first == par) continue;
sz[node] += find_size(a.first, node);
}
}
void dist(int node, int dep, int w, int par, bool ver) {
for (auto a: adj[node]) {
if (a.first == par || seen[a.first]) continue;
dist(a.first, dep + 1, w + l[a.second], node, ver);
}
if (!ver) {
int req = k - w;
if (idx[req] < timer) {
idx[req] = timer, cnt[req] = n + 1;
}
ans = min(ans, dep + cnt[req]);
} else {
int req = w;
if (idx[req] < timer) {
idx[req] = timer, cnt[req] = n + 1;
}
cnt[req] = min(cnt[req], dep);
}
}
void dfs(int node, int par = -1) {
find_size(node);
int c = find_centroid(node, -1, sz[node]);
timer++;
for (auto nxt : adj[c]) {
if (seen[nxt.first]) continue;
dist(nxt.first, 1, l[nxt.second], c, false);
dist(nxt.first, 1, l[nxt.second], c, true);
}
seen[c] = true;
for (auto a : adj[c]) {
if (seen[a.first]) continue;
dfs(a.first);
}
}
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 a = H[i][0], b = H[i][1];
adj[a].push_back({b, i});
adj[b].push_back({a, i});
}
for (int i = 0; i < n-1;i++) l[i] = L[i];
dfs(0);
if (ans >= n +1) {
return -1;
} else return ans;
}
//int main() {
// ios_base::sync_with_stdio(0);
// cin.tie(0); cout.tie(0);
// freopen("race.in", "r", stdin);
// freopen("race.out", "w", stdout);
// cin >> n >> k;
// ans = n + 1;
// for (int i = 0; i < n-1; i++) {
// int a, b; cin >> a >> b;
// adj[a].push_back({b, i}); adj[b].push_back({a, i});
// }
//
// for (int i = 0; i < n-1;i++) cin>> l[i];
//
// dfs(0);
//
// if (ans >= n +1) {
// cout << -1;
// } else cout << ans;
//}
Compilation message
race.cpp: In function 'int find_size(int, int)':
race.cpp:65:1: warning: control reaches end of non-void function [-Wreturn-type]
65 | }
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
194 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
194 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
194 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
194 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
