#include <bits/stdc++.h>
#define ll long long
#define sz(x) (int) x.size()
#define arr array
#define all(x) x.begin(), x.end()
#define len(x) (int) x.length()
using namespace std;
const int INF = 1e9;
const long long INF_LL = 1e18;
const int MOD = 666013;
#define read(x) for (auto &i : x) cin >> i;
void dbg_vInt(string str, vector <int> x) {
cerr << "DBG " << str << '\n';
for (int i = 0; i < sz(x); ++i) {
cerr << "I " << i << " -> " << x[i] << '\n';
}
cerr << '\n';
}
void dbg_bit(int x) {
cerr << "Numero binario " << x << '\n';
for (int i = 0; i < 31; ++i) {
cerr << (x & (1 << i) ? 1 : 0);
}
cerr << '\n';
}
int best_path(int N, int K, int H[][2], int L[]) {
vector <vector <pair <int, int> > > adj (N);
for (int i = 0; i < N - 1; ++i) {
adj[H[i][0]].push_back({H[i][1], L[i]});
adj[H[i][1]].push_back({H[i][0], L[i]});
if (L[i] == K) return 1;
}
vector <unordered_map <int, int> > mappe (N);
int ans = INF;
function <void(int, int, int)> dfs = [&] (int node, int parent, int weigth) -> void {
for (auto &x : adj[node]) {
int to = x.first;
if (to != parent) {
dfs(to, node, x.second);
if (sz(mappe[node]) < sz(mappe[to])) swap(mappe[node], mappe[to]);
for (auto &y : mappe[to]) {
// controllo se esiste un numero che combinato mi trovi il risultato
int search_v = K - y.first;
if (mappe[node].find(search_v) != mappe[node].end()) { // ho il valore -> posso minimizzare il risultato
ans = min(ans, mappe[node][search_v] + y.second);
}
// controllo se e' gia' presente
// true -> minimizzo
// false -> inserisco
if (mappe[node].find(y.first) == mappe[node].end()) {
mappe[node].insert(y);
} else { // vedo se lo minimizzo
mappe[node][y.first] = min(mappe[node][y.first], y.second);
}
}
}
}
// finito di inserire tutti i cammini fino ai figli -> sommo l'arco che sono passato a tutti i valori ->
unordered_map <int, int> new_map;
for (auto &x : mappe[node]) {
ll somma = x.first + weigth;
if (somma > K || x.second + 1 >= ans) continue; // anche se li inserisco non mi servirebbero a niente
if (somma == K) { // posso minimizzare il risultato
ans = min(ans, x.second + 1);
} else {
new_map.insert({(int)somma, x.second + 1});
}
}
new_map.insert({weigth, 1});
// scambio le mappe
swap(new_map, mappe[node]);
};
dfs(0, 0, 0);
return (ans == INF ? -1 : ans);
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
212 KB |
Output is correct |
| 13 |
Correct |
1 ms |
340 KB |
Output is correct |
| 14 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 15 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
212 KB |
Output is correct |
| 13 |
Correct |
1 ms |
340 KB |
Output is correct |
| 14 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 15 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
212 KB |
Output is correct |
| 13 |
Correct |
1 ms |
340 KB |
Output is correct |
| 14 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 15 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
212 KB |
Output is correct |
| 13 |
Correct |
1 ms |
340 KB |
Output is correct |
| 14 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 15 |
Halted |
0 ms |
0 KB |
- |
