| 14567 | 2025-01-16 10:33:33 | Leventusz09 | Medián fában | cpp17 | Time limit exceeded 8/100 | 3.092s | 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<int> 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<int> 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;
long long 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;
}| Subtask | Sum | Test | Verdict | Time | Memory | ||
|---|---|---|---|---|---|---|---|
| subtask1 | 0/0 | ||||||
| 1 | Accepted | 2ms | 1588 KiB | ||||
| 2 | Accepted | 2ms | 1588 KiB | ||||
| subtask2 | 8/8 | ||||||
| 3 | Accepted | 12ms | 2116 KiB | ||||
| 4 | Accepted | 12ms | 2064 KiB | ||||
| 5 | Accepted | 14ms | 1844 KiB | ||||
| 6 | Accepted | 17ms | 2068 KiB | ||||
| 7 | Accepted | 17ms | 2100 KiB | ||||
| 8 | Accepted | 35ms | 2356 KiB | ||||
| 9 | Accepted | 35ms | 2284 KiB | ||||
| subtask3 | 0/19 | ||||||
| 10 | Accepted | 1.687s | 48488 KiB | ||||
| 11 | Accepted | 1.613s | 48436 KiB | ||||
| 12 | Accepted | 2.911s | 48436 KiB | ||||
| 13 | Time limit exceeded | 3.085s | 32052 KiB | ||||
| 14 | Time limit exceeded | 3.082s | 22580 KiB | ||||
| 15 | Time limit exceeded | 3.081s | 47572 KiB | ||||
| 16 | Time limit exceeded | 3.092s | 49760 KiB | ||||
| subtask4 | 0/24 | ||||||
| 17 | Runtime error | 476ms | 262144 KiB | ||||
| 18 | Runtime error | 430ms | 262144 KiB | ||||
| 19 | Runtime error | 476ms | 262144 KiB | ||||
| 20 | Runtime error | 435ms | 262144 KiB | ||||
| 21 | Runtime error | 472ms | 262144 KiB | ||||
| 22 | Runtime error | 428ms | 262144 KiB | ||||
| subtask5 | 0/49 | ||||||
| 23 | Time limit exceeded | 3.086s | 67420 KiB | ||||
| 24 | Time limit exceeded | 3.088s | 65980 KiB | ||||
| 25 | Time limit exceeded | 3.082s | 19508 KiB | ||||
| 26 | Time limit exceeded | 3.082s | 16328 KiB | ||||
| 27 | Time limit exceeded | 3.082s | 25092 KiB | ||||
| 28 | Time limit exceeded | 3.092s | 126780 KiB | ||||
| 29 | Runtime error | 432ms | 262144 KiB | ||||
| 30 | Runtime error | 474ms | 262144 KiB | ||||
| 31 | Runtime error | 432ms | 262144 KiB | ||||
| 32 | Runtime error | 474ms | 262144 KiB | ||||