QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#292053 | #7118. Closing Time | hypeskynick | 18 | 215ms | 43060kb | C++14 | 3.2kb | 2023-12-27 16:44:48 | 2023-12-27 16:44:48 |
Judging History
answer
// Source: https://usaco.guide/general/io
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define pp push
vector<vector<pair<int,ll>>> graph;
vector<bool> vis;
vector<ll> seg1,seg2;
struct node{
ll t;
int x, cnt = 0;
bool operator<(const node &b) const
{
return t < b.t;
}
bool operator>(const node &b) const
{
return b < (*this);
}
};
int greedy(int N, int mx, ll k, ll mdist) {
//cout <<"1\n";
int ans = 0;
vector<int> cnt(N, 0);
priority_queue<node, vector<node>, greater<node>> pqa, pqb;
//cout <<"1\n";
for (int i = 0; i < N; i ++) {
if (mx == 2 && seg1[i] + seg2[i] == mdist) {// case 1 a's
ans++;
cnt[i] ++;
k -= min(seg1[i], seg2[i]);
pqa.pp({abs(seg1[i] - seg2[i]), i, 1});
} else {
pqa.pp({min(seg1[i], seg2[i]), i ,0});
if (mx == 2 ) {// case 2 the b's
pqb.pp({max(seg1[i], seg2[i]), i , 0});
}
}
}
//cout <<"1\n";
auto get_top = [](priority_queue<node, vector<node>, greater<node>> &pq) -> node
{
return pq.empty() ? node{(ll)1e18, (ll)0} : pq.top();
};
auto reduce = [&cnt, &mx, &k](priority_queue<node, vector<node>, greater<node>> &pq) -> void
{
while (!pq.empty() && (cnt[pq.top().x] != pq.top().cnt || k < pq.top().t))
{
pq.pop();
}
};
//cout <<"1\n";
while (!pqa.empty() || !pqb.empty())
{
reduce(pqa);
reduce(pqb);
if (pqa.empty() && pqb.empty())
break;
node one1 = get_top(pqa), one2;
if (!pqa.empty())
{
pqa.pop();
cnt[one1.x]++;
reduce(pqa);
cnt[one1.x]--;
one2 = get_top(pqa);
}
node two = get_top(pqb);
if (pqb.empty() || one1.t + one2.t < two.t)
{
k -= one1.t;
ans++;
cnt[one1.x]++;
if (mx == 2 && cnt[one1.x] == 1)
{
pqa.pp({abs(seg1[one1.x] - seg2[one1.x]), one1.x, 1});
}
}
else
{
pqa.pp(one1);
k -= min(seg1[two.x], seg2[two.x]);
ans++;
cnt[two.x]++;
pqa.pp({abs(seg1[two.x] - seg2[two.x]), two.x, 1});
pqb.pop();
}
}
//cout <<"1\n";
return k < 0 ? 0 : ans;
}
void ddd(vector<ll>& cseg, int node, ll dist) {
vis[node] = true;
cseg[node] = dist;
for (auto [c,w] : graph[node]) {
if (!vis[c]) {
ddd(cseg, c, dist + (ll)w);
}
}
}
int max_score(int N, int X, int Y, ll k, vector<int> U, vector<int> V, vector<int> W) {
graph.resize(N);
seg1.resize(N);
seg2.resize(N);
//cout <<"1\n";
for (int i = 0; i < N - 1; i++) {
graph[U[i]].pb({V[i], W[i]});
graph[V[i]].pb({U[i], W[i]});
}
//travel through "a" values for X
//cout <<"1\n RTE LMFAO";
vis.assign(N,false);
ddd(seg1, X, (ll)0);
//travel through "a" values for Y
vis.assign(N,false);
//cout <<"1\n";
ddd(seg2, Y, (ll)0);
//max of b's and a's for X->Y
//cout <<"1\n";
return max(greedy(N,2, k, seg1[Y]), greedy(N,1, k, seg1[Y]));
//return 1;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 8
Accepted
time: 136ms
memory: 41688kb
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 1 200000 31011 61157 8517583098 31011 129396 964383 1655 129396 331139 1655 191487 566483 110385 191487 865248 43212 110385 542661 43212 81682 13766 81682 91774 546589 91774 124706 780638 124706 175650 118706 10421 175650 615314 10421 151953 436270 140430 151...
output:
081ce3c351cbf526b37954b9ad30f2b531a7585c OK 451
result:
ok
Test #2:
score: 0
Accepted
time: 128ms
memory: 43060kb
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 1 200000 97133 170892 35489415917 114511 170892 730058 34783 114511 435023 34783 47301 562314 47301 162600 457629 44856 162600 365133 44856 133801 83016 117539 133801 124222 117539 128719 199821 77871 128719 703141 77871 133155 624331 7211 133155 138691 7211 ...
output:
081ce3c351cbf526b37954b9ad30f2b531a7585c OK 650
result:
ok
Test #3:
score: -8
Wrong Answer
time: 215ms
memory: 14780kb
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 200 1000 611 992 5736784 504 611 954658 504 936 219278 502 936 632439 393 502 177662 267 393 570266 267 291 941365 291 310 168052 310 765 253098 635 765 724932 274 635 842125 274 799 848645 39 799 433118 39 940 705598 553 940 564063 553 960 69665 917 960 6904...
output:
081ce3c351cbf526b37954b9ad30f2b531a7585c OK 126 49 20 17 23 50 16 33 16 50 44 61 70 10 44 64 36 76 53 33 61 57 37 39 14 35 65 24 23 45 55 51 19 22 49 32 45 43 33 43 46 50 44 40 31 57 29 21 13 35 46 33 45 56 37 51 45 29 8 45 22 56 46 55 53 67 20 43 13 60 40 25 35 31 23 37 31 55 46 34 55 54 40 55 34 5...
result:
wrong answer 2nd lines differ - on the 1st token, expected: '38', found: '49'
Subtask #2:
score: 9
Accepted
Test #4:
score: 9
Accepted
time: 1ms
memory: 3812kb
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 1 50 23 25 382806473 0 1 375710 1 2 898637 2 3 10402 3 4 536577 4 5 385023 5 6 71075 6 7 543368 7 8 301497 8 9 174394 9 10 711312 10 11 923006 11 12 675532 12 13 838667 13 14 565729 14 15 979816 15 16 862618 16 17 576015 17 18 177751 18 19 306989 19 20 881492...
output:
081ce3c351cbf526b37954b9ad30f2b531a7585c OK 96
result:
ok
Test #5:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 1 47 20 22 25669694 0 1 291237 1 2 851987 2 3 421247 3 4 962919 4 5 643085 5 6 224951 6 7 756890 7 8 147295 8 9 625823 9 10 736374 10 11 290526 11 12 335466 12 13 539086 13 14 957449 14 15 423408 15 16 932444 16 17 356032 17 18 307118 18 19 94279 19 20 989546...
output:
081ce3c351cbf526b37954b9ad30f2b531a7585c OK 26
result:
ok
Test #6:
score: 0
Accepted
time: 1ms
memory: 3624kb
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 1 46 6 34 355277954 0 1 574359 1 2 58362 2 3 778155 3 4 538832 4 5 128903 5 6 79774 6 7 715282 7 8 259924 8 9 640303 9 10 361135 10 11 506866 11 12 527045 12 13 946672 13 14 620381 14 15 701743 15 16 766266 16 17 524732 17 18 340089 18 19 630172 19 20 357712 ...
output:
081ce3c351cbf526b37954b9ad30f2b531a7585c OK 74
result:
ok
Test #7:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 1 45 14 44 70669 0 1 266130 1 2 372315 2 3 965349 3 4 119493 4 5 190522 5 6 506822 6 7 45330 7 8 423189 8 9 748532 9 10 653554 10 11 102552 11 12 90431 12 13 843259 13 14 422626 14 15 35334 15 16 1 16 17 1 17 18 1 18 19 1 19 20 1 20 21 1 21 22 1 22 23 1 23 24...
output:
081ce3c351cbf526b37954b9ad30f2b531a7585c OK 4
result:
ok
Test #8:
score: 0
Accepted
time: 1ms
memory: 3760kb
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 1 50 0 49 332340134 0 1 987193 1 2 950856 2 3 893737 3 4 870689 4 5 810192 5 6 790242 6 7 744052 7 8 714922 8 9 677074 9 10 630082 10 11 599644 11 12 528415 12 13 491648 13 14 479486 14 15 439182 15 16 371085 16 17 357776 17 18 308161 18 19 254481 19 20 20430...
output:
081ce3c351cbf526b37954b9ad30f2b531a7585c OK 44
result:
ok
Test #9:
score: 0
Accepted
time: 1ms
memory: 3688kb
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 1 50 0 49 329827838 0 1 972981 1 2 953594 2 3 908629 3 4 849675 4 5 808354 5 6 782643 6 7 759387 7 8 698618 8 9 650896 9 10 639153 10 11 591828 11 12 532588 12 13 503214 13 14 447660 14 15 403224 15 16 380834 16 17 327127 17 18 300115 18 19 244025 19 20 23362...
output:
081ce3c351cbf526b37954b9ad30f2b531a7585c OK 44
result:
ok
Test #10:
score: 0
Accepted
time: 0ms
memory: 3688kb
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 1 3 0 1 1 0 1 1 1 2 1
output:
081ce3c351cbf526b37954b9ad30f2b531a7585c OK 3
result:
ok
Test #11:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 1 20 8 9 31897732 0 1 428932 1 2 103619 2 3 805647 3 4 691922 4 5 320369 5 6 755877 6 7 701672 7 8 426711 8 9 507102 9 10 492732 10 11 68466 11 12 317311 12 13 37666 13 14 499673 14 15 502226 15 16 753200 16 17 523387 17 18 904778 18 19 695859
output:
081ce3c351cbf526b37954b9ad30f2b531a7585c OK 30
result:
ok
Test #12:
score: 0
Accepted
time: 1ms
memory: 3616kb
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 1 20 15 16 25160185 0 1 193268 1 2 139314 2 3 193167 3 4 446469 4 5 793626 5 6 502774 6 7 598587 7 8 69975 8 9 499282 9 10 943594 10 11 804459 11 12 536095 12 13 578060 13 14 142523 14 15 364845 15 16 181397 16 17 64327 17 18 224827 18 19 439557
output:
081ce3c351cbf526b37954b9ad30f2b531a7585c OK 26
result:
ok
Test #13:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 1 20 0 19 77846543 0 1 603320 1 2 433257 2 3 572719 3 4 340716 4 5 549198 5 6 383420 6 7 50703 7 8 720210 8 9 304217 9 10 162280 10 11 68594 11 12 401595 12 13 446738 13 14 920882 14 15 494739 15 16 616729 16 17 874820 17 18 269830 18 19 53532
output:
081ce3c351cbf526b37954b9ad30f2b531a7585c OK 34
result:
ok
Test #14:
score: 0
Accepted
time: 1ms
memory: 3748kb
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 1 19 2 17 6692 0 1 748749 1 2 369010 2 3 3351 3 4 1 4 5 1 5 6 1 6 7 1 7 8 1 8 9 1 9 10 1 10 11 1 11 12 1 12 13 1 13 14 1 14 15 1 15 16 1 16 17 3346 17 18 11355
output:
081ce3c351cbf526b37954b9ad30f2b531a7585c OK 3
result:
ok
Subtask #3:
score: 0
Wrong Answer
Dependency #2:
100%
Accepted
Test #15:
score: 0
Wrong Answer
time: 1ms
memory: 3780kb
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 25 20 9 16 34385 0 1 196 1 2 733 2 3 758 3 4 92 4 5 636 5 6 462 6 7 491 7 8 239 8 9 873 9 10 983 10 11 72 11 12 988 12 13 690 13 14 162 14 15 287 15 16 247 16 17 121 17 18 140 18 19 64 20 9 13 37109 0 1 530 1 2 588 2 3 841 3 4 274 4 5 994 5 6 879 6 7 879 7 8 ...
output:
081ce3c351cbf526b37954b9ad30f2b531a7585c OK 25 26 31 31 29 29 26 27 25 32 28 29 30 28 29 22 27 30 28 30 23 34 34 34 40
result:
wrong answer 2nd lines differ - on the 1st token, expected: '25', found: '26'
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 9
Accepted
Test #36:
score: 9
Accepted
time: 0ms
memory: 3676kb
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 1 4 0 1 9 0 2 2 1 2 3 2 3 3
output:
081ce3c351cbf526b37954b9ad30f2b531a7585c OK 6
result:
ok
Test #37:
score: 0
Accepted
time: 0ms
memory: 3676kb
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 1 4 0 1 8 0 2 2 1 2 3 2 3 100
output:
081ce3c351cbf526b37954b9ad30f2b531a7585c OK 5
result:
ok
Test #38:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 1 8 0 4 84 0 1 1 1 2 29 2 3 29 3 4 1 4 5 20 2 6 20 3 7 1
output:
081ce3c351cbf526b37954b9ad30f2b531a7585c OK 9
result:
ok
Test #39:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 1 18 14 15 221112 8 10 15984 3 8 2664 6 10 5328 9 10 13320 5 10 23976 1 10 13320 3 4 5328 3 7 26640 3 11 23976 4 15 23976 6 17 18648 12 17 5328 11 13 13320 0 11 7992 15 16 5328 2 16 5328 13 14 2664
output:
081ce3c351cbf526b37954b9ad30f2b531a7585c OK 14
result:
ok
Test #40:
score: 0
Accepted
time: 1ms
memory: 3676kb
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 1 19 3 9 11232111 13 14 174955 0 13 69982 10 14 209946 14 15 209946 12 14 104973 0 11 314919 0 3 314919 0 7 139964 5 10 209946 10 16 69982 4 10 104973 9 11 279928 9 17 349910 1 4 104973 3 18 209946 6 18 174955 7 8 314919 2 7 104973
output:
081ce3c351cbf526b37954b9ad30f2b531a7585c OK 28
result:
ok
Test #41:
score: 0
Accepted
time: 0ms
memory: 3696kb
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 1 15 5 7 155966 1 4 964448 5 11 996819 9 10 330180 5 6 987448 11 12 704605 0 5 155967 8 14 596631 10 11 923917 0 14 560902 4 13 49411 1 7 856694 1 12 755799 2 14 488208 3 13 990480
output:
081ce3c351cbf526b37954b9ad30f2b531a7585c OK 2
result:
ok
Test #42:
score: 0
Accepted
time: 1ms
memory: 3684kb
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 1 20 4 7 40726445 15 18 841797 9 16 909512 0 7 39919 8 19 78725 6 17 661904 7 14 426400 17 18 664669 7 13 917960 4 14 821652 4 11 274656 1 12 937782 10 19 129031 12 13 504353 5 11 502915 3 8 264525 2 19 358409 12 18 578659 16 19 696491 3 17 175157
output:
081ce3c351cbf526b37954b9ad30f2b531a7585c OK 30
result:
ok
Test #43:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 1 19 1 8 758761123780644886 3 18 947982 12 13 415218 3 15 890432 11 17 808801 2 8 726510 7 12 752493 8 17 328133 6 7 465830 8 14 126540 9 18 443041 1 7 605214 4 11 243452 9 10 106626 3 7 498126 1 4 39081 0 2 861168 5 15 69635 3 16 223395
output:
081ce3c351cbf526b37954b9ad30f2b531a7585c OK 38
result:
ok
Test #44:
score: 0
Accepted
time: 1ms
memory: 3692kb
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 1 18 4 10 8410500 14 16 912609 2 8 546082 2 12 129063 1 17 454917 15 17 85372 1 11 862697 4 11 428830 7 9 860609 8 10 119165 6 11 143393 14 17 789886 13 15 216341 4 5 56300 12 13 718046 0 7 354300 9 15 142154 1 3 310843
output:
081ce3c351cbf526b37954b9ad30f2b531a7585c OK 11
result:
ok
Test #45:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 1 18 14 15 23103649 0 6 382587 2 4 23201 2 3 58517 0 10 982598 0 17 283539 13 14 944945 4 6 576463 8 14 941541 7 16 566937 1 11 185982 3 9 360540 1 5 441702 4 16 808047 3 14 154737 3 15 344378 9 11 631318 7 12 552451
output:
081ce3c351cbf526b37954b9ad30f2b531a7585c OK 36
result:
ok
Test #46:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 1 18 7 13 25604 13 17 12802 5 14 39262 6 8 774165 2 11 834406 5 6 1 0 16 432886 3 6 1 2 14 272481 5 12 817066 4 9 40750 15 17 889075 1 7 12804 4 16 406687 5 17 1 3 10 875945 0 1 525803 1 3 1
output:
081ce3c351cbf526b37954b9ad30f2b531a7585c OK 3
result:
ok
Test #47:
score: 0
Accepted
time: 0ms
memory: 3740kb
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 1 19 0 8 951764 0 1 4 1 2 4 2 3 4 3 4 307858 4 5 307858 5 6 4 6 7 4 7 8 4 4 9 121363 7 10 4 8 11 214606 5 12 999998 6 13 1000000 1 14 999995 10 15 999997 1 16 999994 13 17 999996 3 18 999991
output:
081ce3c351cbf526b37954b9ad30f2b531a7585c OK 13
result:
ok
Test #48:
score: 0
Accepted
time: 0ms
memory: 3680kb
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 1 20 0 8 274829 0 1 2 1 2 2 2 3 2 3 4 2 4 5 2 5 6 2 6 7 2 7 8 2 4 9 548538 7 10 2 8 11 274686 6 12 999999 0 13 999995 6 14 999992 9 15 1000000 0 16 999997 9 17 999996 3 18 999998 0 19 999999
output:
081ce3c351cbf526b37954b9ad30f2b531a7585c OK 21
result:
ok
Test #49:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 1 18 6 13 58800010 7 11 555657 5 9 283104 0 16 323027 5 11 296013 9 15 584423 1 12 410839 7 13 314886 3 14 890353 4 12 174300 3 12 791983 2 5 216145 4 17 259612 3 16 732206 10 11 976379 8 16 650154 4 9 76441 6 8 589585
output:
081ce3c351cbf526b37954b9ad30f2b531a7585c OK 35
result:
ok
Test #50:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 1 18 5 10 24497819 9 15 154130 7 11 597308 2 11 617436 0 13 517318 3 16 400080 1 5 908978 1 8 181237 4 7 84199 3 6 758216 6 14 32279 11 17 498893 10 12 629338 2 15 180470 10 17 803430 13 16 226223 8 11 134253 4 13 618500
output:
081ce3c351cbf526b37954b9ad30f2b531a7585c OK 26
result:
ok
Test #51:
score: 0
Accepted
time: 1ms
memory: 3616kb
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 1 20 13 17 8319375 13 14 4930 14 18 19720 6 18 104023 1 15 9367 1 19 37961 10 19 1479 14 17 90219 1 11 41905 8 17 986 2 17 4437 8 12 3451 7 12 1479 12 16 3451 3 11 4930 3 5 3944 3 4 4930 0 4 3944 6 15 473280 9 15 4437
output:
081ce3c351cbf526b37954b9ad30f2b531a7585c OK 39
result:
ok
Test #52:
score: 0
Accepted
time: 1ms
memory: 3688kb
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 1 20 6 9 7859406 6 10 3451 4 10 125222 4 7 42891 5 8 17748 3 5 34510 1 3 4930 9 10 69020 5 12 78880 9 11 986 11 16 1972 2 12 1972 0 2 493 0 19 986 18 19 2958 8 15 77894 14 15 77894 13 14 77894 14 17 2958 7 13 77894
output:
081ce3c351cbf526b37954b9ad30f2b531a7585c OK 39
result:
ok
Test #53:
score: 0
Accepted
time: 1ms
memory: 3692kb
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 1 18 9 14 2009 9 17 245 11 17 549633 10 11 419146 10 13 294 0 13 675465 0 4 743232 4 15 245 14 17 147 3 17 490 2 17 392 5 14 294 6 14 98 3 16 49 0 7 294 1 7 343 7 8 98 7 12 98
output:
081ce3c351cbf526b37954b9ad30f2b531a7585c OK 10
result:
ok
Subtask #6:
score: 0
Runtime Error
Dependency #2:
100%
Accepted
Dependency #5:
100%
Accepted
Test #54:
score: 0
Runtime Error
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 5 18 1 13 527703 9 16 351802 9 14 879505 1 9 175901 8 9 879505 9 13 175901 3 9 703604 6 9 175901 1 10 175901 8 17 527703 8 12 703604 5 8 351802 4 17 351802 4 15 175901 3 11 351802 2 6 175901 7 12 175901 0 12 703604 18 4 6 4472320 7 14 279520 0 14 698800 4 14 ...
output:
result:
Subtask #7:
score: 0
Skipped
Dependency #3:
0%
Subtask #8:
score: 0
Skipped
Dependency #4:
0%
Subtask #9:
score: 0
Skipped
Dependency #1:
0%