| 14566 | 2025-01-16 10:29:51 | Leventusz09 | Medián fában | cpp17 | Időlimit túllépés 8/100 | 3.089s | 262144 KiB |
#include <iostream>
#include <vector>
#include <set>
using namespace std;
struct node {
vector<pair<int, int>> et; // i - w
};
node list[50001];
multiset<int> ol;
//bool ty[500001];
/* index; k hossz; előző csúcs; eddigi path; */
void pf(int i, int k, int l, multiset<long long> p) {
node *current = &list[i];
if (p.size() != 0) {
int c = 0, pb = 0;
for (int w : p) {
c++;
pb = w;
if (c == int(k / 2)) break;
}
//ol.push_back(pb);
//if(!ty[i])
ol.insert(pb);
//ty[i] = 1;
}
//if (p.size() == 0) {
for (pair<int, int> t : (*current).et) {
if (t.first != l) {
multiset<long long> tp = p; tp.insert(t.second);
pf(t.first, k + 1, i, tp);
}
}
//}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#define int long long
int N, K;
cin >> N >> K;
for (int i = 0, j, t, w; i < N - 1; i++) {
cin >> j >> t >> w;
list[j].et.push_back({ t, w });
list[t].et.push_back({ j, w });
}
multiset<int> x;
for (int i = 0; i < N; i++) {
pf(i + 1, 1, 0, x);
}
//cout << "\n" << ol.size() << "\n\n";
int c = 0, o1 = 0;
for (int i : ol) {
//cout << i << "\n";
c++; o1 = i;
if (c == K * 2) break;
}
cout << o1;
}| Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
|---|---|---|---|---|---|---|---|
| subtask1 | 0/0 | ||||||
| 1 | Elfogadva | 2ms | 1588 KiB | ||||
| 2 | Elfogadva | 2ms | 1588 KiB | ||||
| subtask2 | 8/8 | ||||||
| 3 | Elfogadva | 12ms | 1912 KiB | ||||
| 4 | Elfogadva | 12ms | 1844 KiB | ||||
| 5 | Elfogadva | 14ms | 2068 KiB | ||||
| 6 | Elfogadva | 17ms | 2064 KiB | ||||
| 7 | Elfogadva | 17ms | 1980 KiB | ||||
| 8 | Elfogadva | 35ms | 2492 KiB | ||||
| 9 | Elfogadva | 35ms | 2348 KiB | ||||
| subtask3 | 0/19 | ||||||
| 10 | Elfogadva | 1.552s | 48448 KiB | ||||
| 11 | Elfogadva | 1.657s | 48436 KiB | ||||
| 12 | Elfogadva | 2.987s | 48604 KiB | ||||
| 13 | Időlimit túllépés | 3.082s | 33024 KiB | ||||
| 14 | Időlimit túllépés | 3.088s | 23348 KiB | ||||
| 15 | Időlimit túllépés | 3.085s | 47668 KiB | ||||
| 16 | Időlimit túllépés | 3.089s | 49716 KiB | ||||
| subtask4 | 0/24 | ||||||
| 17 | Futási hiba | 428ms | 262144 KiB | ||||
| 18 | Futási hiba | 467ms | 262144 KiB | ||||
| 19 | Futási hiba | 472ms | 262144 KiB | ||||
| 20 | Futási hiba | 428ms | 262144 KiB | ||||
| 21 | Futási hiba | 426ms | 262144 KiB | ||||
| 22 | Futási hiba | 425ms | 262144 KiB | ||||
| subtask5 | 0/49 | ||||||
| 23 | Időlimit túllépés | 3.088s | 71808 KiB | ||||
| 24 | Időlimit túllépés | 3.089s | 68000 KiB | ||||
| 25 | Időlimit túllépés | 3.084s | 20688 KiB | ||||
| 26 | Időlimit túllépés | 3.085s | 17204 KiB | ||||
| 27 | Időlimit túllépés | 3.079s | 26116 KiB | ||||
| 28 | Időlimit túllépés | 3.085s | 127792 KiB | ||||
| 29 | Futási hiba | 428ms | 262144 KiB | ||||
| 30 | Futási hiba | 476ms | 262144 KiB | ||||
| 31 | Futási hiba | 437ms | 262144 KiB | ||||
| 32 | Futási hiba | 477ms | 262144 KiB | ||||