QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#879325 | #9696. Analysis | ucup-team139# | WA | 313ms | 58628kb | C++23 | 2.9kb | 2025-02-01 23:35:00 | 2025-02-01 23:35:02 |
Judging History
This is the latest submission verdict.
- [2025-02-06 00:45:32]
- hack成功,自动添加数据
- (/hack/1517)
- [2025-02-01 23:35:00]
- Submitted
answer
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <assert.h>
#include <climits>
#include <iomanip>
using namespace std;
void solve([[maybe_unused]] int t)
{
long long n, A, B;
cin >> n >> A >> B;
vector grafo(n, vector<int>());
for (int i = 0; i < n - 1; i++)
{
int u, v;
cin >> u >> v;
u--;
v--;
grafo[u].push_back(v);
grafo[v].push_back(u);
}
vector dp(n, vector(2, -1ll));
auto f = [&](auto &f, int v, int mode, int last) -> long long
{
if (dp[v][mode] != -1)
return dp[v][mode];
long long res = 0;
if (mode == 1)
{
vector<long long> tmp;
for (auto i : grafo[v])
{
if (i != last)
{
res += A + f(f, i, 0, v);
tmp.push_back(f(f, i, 1, v) - A - f(f, i, 0, v));
}
}
sort(tmp.begin(), tmp.end());
if (tmp.size() > 0)
{
res += tmp[0];
tmp.erase(tmp.begin());
}
for (int i = 0; i < tmp.size(); i += 2)
{
if (tmp[i] + (i + 1 < tmp.size() ? tmp[i + 1] : 0) + B < 0)
{
res += tmp[i] + (i + 1 < tmp.size() ? tmp[i + 1] : 0) + B;
}
else
{
break;
}
}
}
else
{
vector<long long> tmp;
for (auto i : grafo[v])
{
if (i != last)
{
res += A + f(f, i, 0, v);
tmp.push_back(f(f, i, 1, v) - A - f(f, i, 0, v));
}
}
sort(tmp.begin(), tmp.end());
if (tmp.size() > 0)
{
res += B;
res += tmp[0];
tmp.erase(tmp.begin());
}
if (tmp.size() > 0)
{
res += tmp[0];
tmp.erase(tmp.begin());
}
for (int i = 0; i < tmp.size(); i += 2)
{
if (tmp[i] + (i + 1 < tmp.size() ? tmp[i + 1] : 0) + B < 0)
{
res += tmp[i] + (i + 1 < tmp.size() ? tmp[i + 1] : 0) + B;
}
else
{
break;
}
}
}
// cout << v << " " << mode << " " << res << "\n";
return dp[v][mode] = res;
};
cout << f(f, 0, 0, -1) - B << "\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n = 1;
// cin >> n;
for (int i = 1; i <= n; i++)
solve(i);
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3712kb
input:
5 100 1000 1 2 2 3 3 4 4 5
output:
0
result:
ok 1 number(s): "0"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3584kb
input:
5 100 200 1 2 1 3 2 4 2 5
output:
100
result:
ok 1 number(s): "100"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
10 133494816 109943166 10 8 5 3 1 2 8 9 8 5 2 4 8 7 8 6 10 1
output:
219886332
result:
ok 1 number(s): "219886332"
Test #4:
score: 0
Accepted
time: 1ms
memory: 3712kb
input:
10 165074331 854297934 6 2 2 7 9 8 2 9 9 10 6 3 6 4 5 6 6 1
output:
825371655
result:
ok 1 number(s): "825371655"
Test #5:
score: 0
Accepted
time: 1ms
memory: 3712kb
input:
9 719441223 227056392 4 6 9 2 5 3 1 4 6 8 1 9 1 7 3 1
output:
227056392
result:
ok 1 number(s): "227056392"
Test #6:
score: 0
Accepted
time: 1ms
memory: 3712kb
input:
10 216399993 137522662 9 6 1 2 2 9 4 1 10 3 7 5 5 4 3 7 2 8
output:
137522662
result:
ok 1 number(s): "137522662"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
10 796722415 144928611 9 10 6 4 2 7 5 1 3 2 6 5 3 9 1 8 6 3
output:
289857222
result:
ok 1 number(s): "289857222"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
9 377925753 230747764 1 3 8 5 5 1 6 8 7 2 7 4 6 7 7 9
output:
230747764
result:
ok 1 number(s): "230747764"
Test #9:
score: 0
Accepted
time: 1ms
memory: 3840kb
input:
1000 322954853 561443729 978 218 369 277 32 327 665 398 950 674 723 693 426 803 188 866 857 272 644 704 419 303 884 872 178 742 884 903 499 104 832 692 585 636 215 68 369 911 672 796 908 852 971 948 497 825 319 193 524 845 94 651 669 210 529 963 326 877 56 310 707 447 722 388 881 945 605 757 140 521...
output:
156210605808
result:
ok 1 number(s): "156210605808"
Test #10:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
1000 921029898 839745690 143 605 601 220 606 11 722 857 603 448 328 773 696 504 524 68 247 119 416 398 646 956 864 414 727 136 156 354 182 559 286 928 439 312 57 849 48 348 559 563 417 982 769 868 179 915 40 480 396 979 377 716 226 177 996 395 188 977 692 634 183 349 581 36 787 227 891 850 73 137 90...
output:
277955823390
result:
ok 1 number(s): "277955823390"
Test #11:
score: 0
Accepted
time: 1ms
memory: 3840kb
input:
970 865003183 730298972 199 701 485 267 822 192 167 635 636 848 438 566 924 5 11 222 576 420 509 432 428 630 251 832 860 510 306 299 147 817 190 764 126 413 693 156 546 72 672 868 929 312 513 260 920 803 112 947 302 316 875 615 566 587 321 369 889 645 819 692 255 735 450 523 824 397 509 300 167 353 ...
output:
240998660760
result:
ok 1 number(s): "240998660760"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
1000 862859507 141216120 116 532 374 648 795 283 346 28 787 724 336 17 936 385 293 829 704 161 1 816 2 483 931 82 417 565 828 451 774 276 476 401 447 696 234 769 930 847 496 578 458 536 226 301 244 902 682 977 738 657 337 39 235 124 571 751 364 50 88 556 54 444 804 352 96 120 642 970 533 213 740 776...
output:
33609436560
result:
ok 1 number(s): "33609436560"
Test #13:
score: 0
Accepted
time: 1ms
memory: 3840kb
input:
1000 558366571 505493045 489 545 912 759 682 374 19 582 343 297 393 769 440 361 589 29 12 393 253 348 190 323 286 193 221 42 453 593 310 638 966 761 646 780 292 401 123 31 695 515 846 802 436 471 232 594 198 650 834 242 17 301 775 942 475 41 332 535 64 479 760 766 752 150 591 195 310 712 536 416 560...
output:
119801851665
result:
ok 1 number(s): "119801851665"
Test #14:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
970 935970558 426067204 636 310 658 635 469 629 615 193 346 166 256 932 847 1 301 697 106 259 645 352 240 79 102 908 873 617 625 354 887 209 876 525 354 543 843 369 348 90 264 892 232 31 752 934 88 730 670 957 722 575 606 650 410 468 720 603 785 351 109 528 467 58 239 504 107 806 402 533 961 660 315...
output:
100551860144
result:
ok 1 number(s): "100551860144"
Test #15:
score: 0
Accepted
time: 313ms
memory: 58628kb
input:
500000 854171423 776249842 139098 351774 367457 487287 175143 435875 131857 395707 160145 78070 430794 234221 196215 268128 238673 209485 102068 166268 13331 411244 123088 54536 113149 55054 463338 308892 144261 442906 194976 240811 392302 303426 56316 276955 223558 229936 354466 364582 175540 30642...
output:
129178064956746
result:
ok 1 number(s): "129178064956746"
Test #16:
score: 0
Accepted
time: 297ms
memory: 57772kb
input:
493243 273965898 224990156 218586 487842 169177 471606 145650 330516 368949 418196 244612 431071 417446 407540 225235 182582 481785 387884 188870 368395 117071 290711 75134 22877 294614 91575 215711 163402 91686 127432 337291 433398 480599 365175 187020 292618 210054 164142 317950 488724 232843 3021...
output:
37049578968832
result:
ok 1 number(s): "37049578968832"
Test #17:
score: 0
Accepted
time: 293ms
memory: 57328kb
input:
488126 782505765 760857298 290095 354815 401202 249622 116534 461355 15189 354691 48189 411672 68619 226381 103976 450020 273367 131977 367786 400433 76697 111085 211550 315456 372878 125870 126388 467891 147731 64354 248125 228698 138125 298745 172808 241811 193855 454527 117671 17601 109584 153374...
output:
123697896936946
result:
ok 1 number(s): "123697896936946"
Test #18:
score: 0
Accepted
time: 304ms
memory: 58624kb
input:
500000 466056790 251466232 299560 359515 8444 202278 307923 223463 288862 295421 111000 434937 412214 423184 301363 243058 269095 62467 335738 88086 340322 169116 34205 395799 405652 250981 105714 220549 87849 169294 277687 429426 225867 46568 450624 91701 42645 216689 394332 384787 438993 222565 18...
output:
41870384959160
result:
ok 1 number(s): "41870384959160"
Test #19:
score: 0
Accepted
time: 308ms
memory: 57864kb
input:
493243 573252828 66338508 419359 306156 251109 152438 26779 97738 309450 296418 373858 396418 448991 22564 430724 185463 299545 425898 437084 78551 139638 404678 111173 175392 297708 440989 89818 243571 399226 400780 489097 281923 11028 367193 333327 453026 176869 224530 39615 472178 206594 195606 1...
output:
10889399749692
result:
ok 1 number(s): "10889399749692"
Test #20:
score: 0
Accepted
time: 295ms
memory: 57332kb
input:
488126 972949106 602615933 388528 63391 9531 33183 212757 36927 438731 436006 422330 405413 146853 165100 162875 69347 23332 471508 413579 53583 189773 168863 474346 401848 227727 145742 275253 469471 90147 449351 25157 120955 75658 402250 324537 298973 437165 279589 452249 7884 355052 384472 123287...
output:
98051638458430
result:
ok 1 number(s): "98051638458430"
Test #21:
score: -100
Wrong Answer
time: 306ms
memory: 58624kb
input:
500000 90278906 978879417 358944 493867 493203 354507 409295 98147 389389 125183 162034 468622 163783 39977 415208 82592 156372 265725 345117 427435 118503 471786 99375 284747 487964 319889 474855 206569 210299 134145 259364 205684 359379 56978 164073 297096 64233 393022 294365 279170 376041 55007 1...
output:
71633683603162
result:
wrong answer 1st numbers differ - expected: '42920682975858', found: '71633683603162'