QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#686131 | #1992. Delegation | makrav | 0 | 0ms | 0kb | C++20 | 3.0kb | 2024-10-29 00:58:53 | 2024-10-29 00:58:54 |
answer
#include <bits/stdc++.h>
#include <cassert>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pb push_back
#define ff first
#define sc second
void solve() {
int n; cin >> n;
vector<vector<int>> g(n);
for (int i = 0; i < n - 1; i++) {
int u, v; cin >> u >> v;
u--; v--;
g[u].pb(v);
g[v].pb(u);
}
auto check = [&](int k) {
bool bad = false;
auto dfs = [&](int v, int p, auto&&self) -> int {
vector<int> paths;
for (int u : g[v]) {
if (u != p) {
paths.pb(1 + self(u, v, self));
}
}
if (paths.empty()) return 0;
sort(all(paths));
int ind_last = -1;
for (int i = 0; i < sz(paths); i++) {
if (paths[i] < (k + 1) / 2) ind_last = i;
}
int sec_hf = paths.size() - ind_last - 1;
int big = 0;
for (int i = 0; i < sz(paths); i++) big += (paths[i] >= k);
auto check2 = [&](int wi) {
int i2 = ind_last + 1;
int big_ost = big, so = sec_hf - big;
for (int i = ind_last; i >= 0; i--) {
if (wi == i) continue;
while (i2 < sz(paths) && (paths[i2] + paths[i] < k || wi == i2)) i2++;
if (i2 == sz(paths)) return false;
if (paths[i2] >= k) big_ost--;
else so--;
i2++;
}
if (wi != -1) {
if (paths[wi] >= k) big_ost--;
else if (paths[wi] >= (k + 1) / 2) so--;
}
if ((big_ost + so) % 2 == 0 || big_ost) return true;
return false;
};
if (v == 0) {
return check2(-1);
} else {
int L = -1, R = sz(paths);
while (R - L > 1) {
int M = (L + R) / 2;
if (check2(M)) L = M;
else R = M;
}
if (L == -1) {
if (check2(-1)) {
bad = true;
}
return 0;
}
return (L == -1 ? 0 : paths[L]);
}
};
return (dfs(0, 0, dfs) && !bad);
};
int L = 1, R = n;
while (R - L > 1) {
int M = (L + R) / 2;
if (check(M)) L = M;
else R = M;
}
cout << L << '\n';
}
signed main() {
int tt = 1;
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
cin >> tt;
#else
freopen("deleg.in", "r", stdin);
freopen("deleg.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
#endif
while (tt--) {
solve();
}
return 0;
}
詳細信息
Pretests
Final Tests
Test #1:
score: 0
Dangerous Syscalls
input:
8 1 2 1 3 1 4 4 5 1 6 6 7 7 8
output:
result:
Test #2:
score: 0
Dangerous Syscalls
input:
100000 42743 91269 60287 46253 76725 22493 23300 66302 91496 69574 65622 64561 6516 70616 49959 8029 51708 15347 6859 88839 43640 98789 57986 52803 3959 4125 93798 43129 16682 93972 160 56491 422 72568 2686 63066 26023 24949 15240 57563 42523 31152 84419 47194 73581 66089 94869 13921 14619 62437 250...
output:
result:
Test #3:
score: 0
Dangerous Syscalls
input:
100000 53180 6939 99397 71477 78037 86531 64650 16151 94386 68554 42692 94131 19325 24762 69636 36799 1285 49037 77536 92511 37894 62016 72736 47527 85261 47929 31428 20305 34905 72359 8720 33731 52830 14918 64384 30766 97468 1774 77786 36045 58662 39178 30912 58176 45324 72450 92204 88912 56702 773...
output:
result:
Test #4:
score: 0
Dangerous Syscalls
input:
100000 88943 43091 9982 20310 81813 57358 39368 12085 39025 88597 9513 77396 77034 46264 72005 37811 4869 82648 16034 65501 29439 60061 73160 99736 87406 18277 83667 27801 47539 62604 1125 76589 17370 53737 94792 28479 10711 43412 25064 55279 76334 36140 2253 94795 27584 39016 48909 93748 20794 8994...
output:
result:
Test #5:
score: 0
Dangerous Syscalls
input:
1000 430 690 116 565 258 985 129 690 109 836 501 690 142 282 867 901 97 462 598 68 61 919 371 767 756 785 902 258 679 980 479 717 332 690 434 856 853 241 834 400 347 557 692 593 31 929 774 333 167 258 398 543 690 25 917 875 104 103 694 258 591 258 258 180 38 409 373 726 63 628 213 475 170 201 394 73...
output:
result:
Test #6:
score: 0
Dangerous Syscalls
input:
1000 748 911 632 973 701 838 319 917 677 649 29 23 942 97 783 21 421 97 901 229 727 478 645 97 22 277 97 731 823 507 375 457 97 887 537 497 542 711 411 244 97 137 418 685 686 261 642 302 97 816 383 596 3 908 893 829 489 741 820 102 97 844 91 676 304 830 999 475 631 927 225 221 576 581 377 97 986 97 ...
output:
result:
Test #7:
score: 0
Dangerous Syscalls
input:
1000 890 32 356 920 383 45 14 986 871 467 288 345 740 184 717 813 776 373 463 60 594 355 782 724 86 53 211 798 912 772 640 504 258 436 441 150 325 62 286 290 580 691 69 407 228 953 174 797 756 298 534 606 134 633 91 251 700 426 909 418 79 601 623 435 787 632 692 906 295 427 751 174 786 896 528 642 7...
output:
result:
Test #8:
score: 0
Dangerous Syscalls
input:
1000 550 782 946 562 337 777 413 290 689 398 166 987 980 893 805 47 184 352 521 643 155 613 310 748 702 388 976 260 257 117 290 680 978 314 381 942 294 657 691 687 814 105 180 889 59 94 650 764 872 73 890 712 311 110 709 916 823 695 291 688 846 437 675 497 920 924 317 880 487 879 630 177 700 23 589 ...
output:
result:
Test #9:
score: 0
Dangerous Syscalls
input:
100000 82345 90270 42331 4456 68627 54437 56398 52140 75192 98569 68278 29727 42050 28427 97215 18603 45035 12841 60648 2113 56398 87935 7839 56147 65916 44655 88758 61752 72482 30185 82868 79081 49065 96956 56398 45283 1920 80976 56398 196 74653 44623 70428 62938 85292 93271 65397 37384 7109 5851 7...
output:
result:
Test #10:
score: 0
Dangerous Syscalls
input:
100000 61777 67318 71721 340 63959 15212 66318 48135 21171 18484 80484 62778 6679 76873 45624 95860 73698 32281 77479 24525 28632 17960 64822 13460 53021 86835 76932 56282 30950 9413 53829 60638 77769 30899 8256 9023 99828 65138 75859 29973 80610 22743 48189 70494 37412 81258 20826 12082 34210 26400...
output:
result:
Test #11:
score: 0
Dangerous Syscalls
input:
100000 90003 90024 78780 8760 25349 91480 52562 9193 68702 59049 14357 5473 62985 10463 60036 2218 72482 5160 62593 78451 86213 73352 75943 993 9362 71309 85653 11739 80682 2734 35325 43139 91964 33551 5000 54739 44494 33720 90539 25314 62933 80682 47955 89358 6929 84776 30623 41508 56016 71783 4811...
output:
result:
Test #12:
score: 0
Dangerous Syscalls
input:
100000 55486 10345 76527 16779 28947 87307 87785 58220 65818 59650 94872 22531 42896 52137 70379 36966 41371 53288 43172 39469 31849 64620 27761 2412 39271 50755 15759 26100 17021 81028 5849 87303 7810 24052 29645 37035 70862 84351 24620 5570 32375 54080 62223 40353 8042 83779 70896 34121 60010 4410...
output:
result:
Test #13:
score: 0
Dangerous Syscalls
input:
100000 11913 3318 82661 17409 57548 26550 93953 99744 94733 51556 51768 21036 78354 79579 46614 83434 21732 59184 82080 47642 87483 66896 21578 34011 39785 64760 78701 63999 31291 12798 31873 9346 74984 78554 39925 9736 82259 57849 26657 34065 14172 80873 56077 70916 46513 21676 77235 29351 5150 231...
output:
result:
Test #14:
score: 0
Dangerous Syscalls
input:
100000 21528 3607 66159 94771 39441 70661 20753 22608 77091 19478 50599 66305 18758 79918 27127 17912 58317 6380 11368 60772 27499 18533 89142 97032 84346 20545 41934 33081 42632 40204 55294 68499 95492 45187 94332 25181 18830 31209 15826 57327 64991 17639 28163 79433 58852 49520 1405 15206 48083 83...
output:
result:
Test #15:
score: 0
Dangerous Syscalls
input:
100000 16001 99590 14751 61584 11186 77808 59021 97757 56374 73393 37092 80674 43555 86476 16942 33028 3065 45171 16870 71040 3589 56589 38330 17402 9634 19554 5290 84289 5091 99081 88038 27562 50918 89139 18268 5737 78832 27234 87816 49562 54740 39909 62373 37228 56703 76102 76985 93575 67156 79894...