QOJ.ac
QOJ
QOJ is currently under a maintenance. It might be unavailable in the following a few hours.
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #940866 | #393. Signaling | ltunjic# | 0 | 1ms | 4224kb | C++20 | 1.4kb | 2025-03-18 04:06:05 | 2025-03-18 04:06:06 |
Judging History
answer
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#define X first
#define Y second
#define PB push_back
using namespace std;
typedef pair<int, int> pii;
const int N = 1e5 + 10;
int largest(vector<pii> &v, int k, int x) {
int ret = 0;
for(int i = 0, j = 0; i < (int) v.size() && j < k; ++i) {
if(v[i].Y != x) {
ret += v[i].X;
++j;
}
}
return ret;
}
int n, k;
vector<int> g[N];
int k1[N], k2[N], tro[N], mx[N];
void solve(int u, int p) {
vector<pii> ch;
for(int v : g[u]) {
if(v != p) {
solve(v, u);
k1[u] = max(k1[u], k1[v]);
k2[u] = max(k2[u], k2[v]);
tro[u] = max(tro[u], tro[v] + 1);
ch.PB({mx[v] + 1, v});
}
}
sort(ch.begin(), ch.end());
reverse(ch.begin(), ch.end());
mx[u] = largest(ch, 1, -1);
tro[u] = max(tro[u], largest(ch, 3, -1));
k1[u] = max(k1[u], largest(ch, 2, -1));
k2[u] = max(k2[u], largest(ch, 4, -1));
for(int v : g[u]) {
if(v != p) {
k2[u] = max(k2[u], largest(ch, 2, v) + k1[v]);
k2[u] = max(k2[u], largest(ch, 1, v) + tro[v] + 1);
}
}
// printf("%d %d %d %d\n", u, mx[u], k1[u], k2[u]);
}
int main() {
scanf("%d%d", &n, &k);
for(int i = 0; i < n - 1; ++i) {
int u, v;
scanf("%d%d", &u, &v);
g[u].PB(v);
g[v].PB(u);
}
solve(1, 0);
printf("%d\n", (n - 1) * 2 + k - (k == 1 ? k1[1] : k2[1]));
return 0;
}
詳細信息
Pretests
Final Tests
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3840kb
input:
10 -50 46 12 -45 -75 -9 63 -90 -55 58 34 -93 12 -56 -39 -92 -94 2 -97 56
output:
-32
result:
wrong answer 1st numbers differ - expected: '5.91667', found: '-32.00000', error = '6.40845'
Test #2:
score: 0
Wrong Answer
time: 1ms
memory: 3712kb
input:
20 -92 -19 54 50 -73 8 31 99 -87 77 100 -23 27 71 70 47 -66 -61 -95 51 -69 -35 -72 22 -77 -54 -68 53 50 -32 -43 -42 3 59 -95 3 -7 -2 -43 -64
output:
-54
result:
wrong answer 1st numbers differ - expected: '10.38333', found: '-54.00000', error = '6.20064'
Test #3:
score: 0
Wrong Answer
time: 0ms
memory: 4096kb
input:
50 -453 9273 8635 5374 7799 -7270 4790 5371 -4527 7088 -5703 116 1861 413 4233 -8269 -806 -6547 2147 -6368 6555 -7298 56 -2857 2201 7138 938 7735 -5991 3010 -2957 382 -8048 2456 449 -9863 -9972 8117 558 7923 -9198 -9065 -8252 5549 -7689 939 -3073 -9730 5708 -8504 -3763 -9209 7681 2139 5616 -4776 280...
output:
-355
result:
wrong answer 1st numbers differ - expected: '23.31775', found: '-355.00000', error = '16.22445'
Test #4:
score: 0
Wrong Answer
time: 0ms
memory: 4224kb
input:
100 -2141 -4880 -9922 -5732 -1447 6911 -1075 -6956 -6494 -3573 8708 6799 4213 2423 6020 -1331 8680 4477 -8039 -2826 -7634 -528 -2889 -9898 4520 -6714 -2444 -4444 1162 1172 -2956 -6434 -8580 4504 -4828 837 7455 6831 -3319 2977 6809 -6073 7342 4840 6805 -1347 6238 6681 -1140 7819 6874 3130 -1002 -9025...
output:
-1943
result:
wrong answer 1st numbers differ - expected: '44.23919', found: '-1943.00000', error = '44.92033'
Test #5:
score: 0
Runtime Error
input:
200 -1122 14370 -42358 19597 -8142 -62821 -96727 50998 -39983 -1255 -9889 -32277 -76715 -26038 56558 30000 40878 -16623 -48090 -48731 15995 -5641 75446 -54677 63957 10714 -73685 58774 -51402 -9966 43245 13215 64833 62221 -33150 -97182 -57948 -30006 -39542 -59193 75510 70480 54803 6772 -20806 -42135 ...
output:
result:
Test #6:
score: 0
Runtime Error
input:
450 311476 420680 -179437 -453868 692958 -289805 882929 -536362 -635778 -76866 -452292 737474 -319376 -97126 -436325 -624165 -830541 -235691 -32100 -25859 269774 -319553 -952967 -665867 -759030 -379696 -799622 531046 162770 929102 959448 -820442 -696548 250017 315619 869226 -950422 483601 -238243 92...
output:
result:
Test #7:
score: 0
Runtime Error
input:
500 901932 -831127 177611 -452336 -81615 -260260 -868737 915377 -805269 -567574 -621357 -983383 -478831 -753449 -146546 929599 -705635 256170 55217 -697919 -708568 -316283 720771 -686336 568982 851708 569161 638609 -641368 -750581 -247391 301211 -342708 673355 393219 -184972 -676469 154890 -559945 8...
output:
result:
Test #8:
score: 0
Runtime Error
input:
1000 618441 536922 -670652 756937 -951203 -88976 -96750 102377 -49403 267613 -202790 492478 328782 -572207 -401320 -225835 -533681 -451907 298806 -554354 -933347 -292249 -396171 -911579 -211258 458880 60941 -128449 -856581 -816717 -782661 221946 219834 -400346 531242 -745577 -789282 -735078 253598 5...
output:
result:
Test #9:
score: 0
Runtime Error
input:
1500 -466267 -545644 842097 -947922 699094 -376679 708277 42478 712256 813305 -629139 377724 795013 -265652 885435 362587 105505 -151452 419402 618775 -824399 431939 936446 382165 -227899 -244470 476667 778569 -349480 729226 -248801 -328251 -829799 -147620 270009 -822539 -760492 814759 -278341 -5627...
output:
result:
Test #10:
score: 0
Runtime Error
input:
1500 372361 -892254 674948 369064 663890 427706 -962493 -748469 -296124 -837649 366715 89587 414772 -877335 -788861 594332 -306600 -691 -443204 -140585 325874 -187797 -549930 -649347 -689284 -598867 -174278 921052 -691067 551110 -491282 -305052 439793 -153742 858640 165072 141049 845958 -974583 3462...