| 14568 | 2025-01-16 10:53:45 | Leventusz09 | Medián fában | cpp17 | Time limit exceeded 8/100 | 3.098s | 262144 KiB |
#include <iostream>
#include <vector>
#include <set>
using namespace std;
vector<pair<int, int>> et[50001]; // 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];
vector<pair<int, int>>* current = &et[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) {
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;
et[j].push_back({ t,w });
et[t].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 | 2060 KiB | ||||
| 4 | Accepted | 12ms | 1844 KiB | ||||
| 5 | Accepted | 16ms | 1844 KiB | ||||
| 6 | Accepted | 17ms | 2048 KiB | ||||
| 7 | Accepted | 18ms | 2100 KiB | ||||
| 8 | Accepted | 37ms | 2356 KiB | ||||
| 9 | Accepted | 37ms | 2284 KiB | ||||
| subtask3 | 0/19 | ||||||
| 10 | Accepted | 1.705s | 48436 KiB | ||||
| 11 | Accepted | 1.648s | 48436 KiB | ||||
| 12 | Time limit exceeded | 3.089s | 48432 KiB | ||||
| 13 | Time limit exceeded | 3.086s | 31796 KiB | ||||
| 14 | Time limit exceeded | 3.086s | 22464 KiB | ||||
| 15 | Time limit exceeded | 3.086s | 47528 KiB | ||||
| 16 | Time limit exceeded | 3.088s | 49940 KiB | ||||
| subtask4 | 0/24 | ||||||
| 17 | Runtime error | 433ms | 262144 KiB | ||||
| 18 | Runtime error | 476ms | 262144 KiB | ||||
| 19 | Runtime error | 430ms | 262144 KiB | ||||
| 20 | Runtime error | 476ms | 262144 KiB | ||||
| 21 | Runtime error | 430ms | 262144 KiB | ||||
| 22 | Runtime error | 470ms | 262144 KiB | ||||
| subtask5 | 0/49 | ||||||
| 23 | Time limit exceeded | 3.079s | 65404 KiB | ||||
| 24 | Time limit exceeded | 3.081s | 65256 KiB | ||||
| 25 | Time limit exceeded | 3.076s | 18880 KiB | ||||
| 26 | Time limit exceeded | 3.076s | 16112 KiB | ||||
| 27 | Time limit exceeded | 3.092s | 25008 KiB | ||||
| 28 | Time limit exceeded | 3.098s | 126784 KiB | ||||
| 29 | Runtime error | 476ms | 262144 KiB | ||||
| 30 | Runtime error | 432ms | 262144 KiB | ||||
| 31 | Runtime error | 432ms | 262144 KiB | ||||
| 32 | Runtime error | 474ms | 262144 KiB | ||||