QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#628603 | #9349. Exchanging Gifts | Lnian | AC ✓ | 276ms | 71004kb | C++20 | 2.3kb | 2024-10-10 21:10:06 | 2024-10-10 21:10:07 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
#define pll pair<ll, ll>
#define pii pair<int, int>
#define vi vector<int>
#define fir(i, a, b) for (int i = a; i <= b; i++)
#define pqi priority_queue<int> // 优先队列
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
// #define int long long
void solve()
{
int n;
std::cin >> n;
std::vector<std::vector<int>> q(n);
std::vector<int> k(n), x(n), y(n), o(n), m(n);
std::vector<i64> len(n), c(n);
for (int i = 0; i < n; i++)
{
std::cin >> o[i];
if (o[i] == 1)
{
std::cin >> k[i];
q[i].resize(k[i]);
for (int j = 0; j < k[i]; j++)
{
std::cin >> q[i][j];
if (m[i] == q[i][j] || c[i] == 0)
{
m[i] = q[i][j];
c[i]++;
}
else
{
c[i]--;
}
}
len[i] = k[i];
}
else
{
std::cin >> x[i] >> y[i];
x[i]--;
y[i]--;
len[i] = len[x[i]] + len[y[i]];
if (m[x[i]] == m[y[i]])
{
m[i] = m[x[i]];
c[i] = c[x[i]] + c[y[i]];
}
else if (c[x[i]] > c[y[i]])
{
m[i] = m[x[i]];
c[i] = c[x[i]] - c[y[i]];
}
else
{
m[i] = m[y[i]];
c[i] = c[y[i]] - c[x[i]];
}
}
}
int v = m[n - 1];
for (int i = 0; i < n; i++)
{
if (o[i] == 1)
{
c[i] = 0;
for (auto x : q[i])
{
c[i] += (x == v);
}
}
else
{
c[i] = c[x[i]] + c[y[i]];
}
}
i64 ans = std::min(len[n - 1], 2 * (len[n - 1] - c[n - 1]));
std::cout << ans << "\n";
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t;
std::cin >> t;
while (t--)
{
solve();
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3560kb
input:
2 1 1 5 3 3 2 1 3 3 1 3 3 3 2 1 4 2 2 3 3 2 1 2
output:
4 6
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 153ms
memory: 3868kb
input:
10000 100 1 30 371028678 371028678 371028678 716418076 398221499 591504380 398221499 398221499 591504380 777141390 398221499 591504380 591504380 777141390 287847807 716418076 777141390 716418076 777141390 287847807 287847807 287847807 371028678 371028678 398221499 777141390 371028678 6827702 6827702...
output:
700 68 332 284 131 1048 194 667 704 0 484 252 35 351 1228 238 1025 354 383 571 4272 340 1044 199 448 190 0 69 841 546 247 883 138 1633 91 3308 2556 1280 488 618 407 381 383 2865 0 496 1202 53 0 415 662 380 41 18 91 505 818 603 241 764 1227 1802 176 187 817 1489 460 296 238 236 1028 0 606 1696 746 10...
result:
ok 10000 lines
Test #3:
score: 0
Accepted
time: 159ms
memory: 3724kb
input:
1000 1000 1 95 626416845 75969860 75969860 75969860 75969860 75969860 626416845 75969860 626416845 626416845 626416845 626416845 75969860 75969860 75969860 626416845 75969860 626416845 626416845 75969860 626416845 75969860 75969860 626416845 75969860 626416845 626416845 75969860 75969860 75969860 62...
output:
7496 113951 17628 151136 92998 49984 39422 57746 0 28271 27458 0 127054 13854 68249 32166 280419 70120 0 0 47941 71104 93032 21042 30012 0 0 14482 20938 66600 94605 129973 145603 16366 43924 0 9923 18731 0 249292 8847 30154 288759 0 86256 30372 156418 247862 91672 38330 89806 27911 137951 166924 189...
result:
ok 1000 lines
Test #4:
score: 0
Accepted
time: 165ms
memory: 4312kb
input:
100 10000 1 1354 265069553 265069553 729542591 729542591 729542591 729542591 729542591 729542591 729542591 265069553 265069553 265069553 729542591 729542591 265069553 729542591 265069553 729542591 265069553 729542591 265069553 265069553 265069553 265069553 265069553 265069553 729542591 265069553 265...
output:
2156412 5940042 1932718 2497609 3287092 0 5176818 7057040 26127674 6268925 0 3298524 6134142 0 0 0 2293094 0 67966 0 708927 0 3540522 205067 0 791702 3283922 0 5278171 8734406 3719656 0 5635776 3559716 0 5795392 4238756 1752825 0 17244508 398074 0 12989840 0 0 849320 211188 545453 4409794 0 4164304 ...
result:
ok 100 lines
Test #5:
score: 0
Accepted
time: 203ms
memory: 9528kb
input:
10 100000 1 11020 495408904 495408904 377631092 377631092 377631092 377631092 495408904 377631092 377631092 377631092 495408904 377631092 495408904 495408904 377631092 495408904 495408904 495408904 377631092 495408904 377631092 495408904 377631092 495408904 495408904 495408904 495408904 377631092 49...
output:
306812544 192374690 0 0 19322750 795133717 1281613237 77446187 657488136 227127642
result:
ok 10 lines
Test #6:
score: 0
Accepted
time: 165ms
memory: 9420kb
input:
10 100000 1 10000 721377195 837302194 866508535 947346285 36266706 885676668 931769731 950140113 336739676 477767858 708236246 553944300 378949767 850666110 754246821 53462385 667372368 691425789 878638555 396531344 888905673 113446879 829163879 489125321 788813861 642102926 385958067 714854335 6508...
output:
535195874754560000 535195874754560000 133801653043210000 133801655190683648 535195874754560000 133819245229244416 535195874754560000 133872021787377664 535195874754560000 133801653043265536
result:
ok 10 lines
Test #7:
score: 0
Accepted
time: 166ms
memory: 9656kb
input:
10 100000 1 1000 55640705 589038906 352151492 603244663 896314553 860752431 500209454 56094027 371761203 363949205 501227909 532363958 763599732 95675505 312353609 918986340 123342067 761471031 178556744 700207408 656301242 711885091 587922713 586430924 876540773 229555768 757856715 173237529 180645...
output:
104016591716353000 104016592253222912 104016591716353000 104016591716353000 416057776930816000 105142491623194624 104016591716353000 416057776930816000 104016591716353000 416057776930816000
result:
ok 10 lines
Test #8:
score: 0
Accepted
time: 177ms
memory: 9676kb
input:
10 100000 1 100 988785552 3909798 727351943 399874018 318067590 95313920 948133144 564913802 648297450 836277365 217035651 602026122 891026470 882991592 809937965 425050760 324253635 781739568 820005774 621599149 349939432 750912678 751600353 864942651 533974868 219178369 407006878 582234094 4585215...
output:
111629635996876900 446504800092160000 446504800092160000 111911110973587456 111629636265312256 111629635996876900 111629635996876900 111629635996876900 446504800092160000 446504800092160000
result:
ok 10 lines
Test #9:
score: 0
Accepted
time: 136ms
memory: 3632kb
input:
1000 1000 1 100 579726539 243218660 784343939 306560155 789028819 972534 2261299 798479785 286504787 706892485 955705857 874653367 22826788 342428009 294524035 698002616 394994586 745415390 119214797 787291501 31196213 674902174 53229014 787260449 853906699 234365182 499771467 929862265 164170850 86...
output:
63002050631303168 251128455784038400 251128455784038400 63002016271564816 63002016271564801 251128455784038400 63002291149471744 251128455784038400 251128455784038400 63002050631303168 251128455784038400 63002020566532096 63002020566532096 251128455784038400 251128455784038400 251128455784038400 251...
result:
ok 1000 lines
Test #10:
score: 0
Accepted
time: 133ms
memory: 3576kb
input:
10000 100 1 33 621712527 94542753 877722940 91794599 852192999 796830698 565357017 448631434 184232487 132101855 405645073 825549849 643026324 362068952 124630665 807882475 297088933 77415771 805839822 170166929 202085947 361117991 831243363 508249456 880121153 362068952 751277937 653563682 66775376...
output:
34619392 69206016 69206016 69206016 69206016 69206016 34603009 69206016 69206016 34603072 34603136 34635776 35651584 35651584 69206016 34603010 68157440 34603012 34603264 69206016 34603041 69206016 69206016 69206016 69206016 69206016 69206016 34611200 69206016 69206016 34603010 69206016 35651584 692...
result:
ok 10000 lines
Test #11:
score: 0
Accepted
time: 142ms
memory: 64872kb
input:
1 1000000 1 250000 922489025 888688165 883481805 939430294 105098992 979655134 109879600 548634372 904050132 269745155 541775148 720841524 220842343 544036480 577115868 772090385 473808263 378851841 844743186 975484874 247231077 409042180 172984502 893406283 906335132 320482926 92038319 638422659 57...
output:
524225085440000000
result:
ok single line: '524225085440000000'
Test #12:
score: 0
Accepted
time: 164ms
memory: 64876kb
input:
1 1000000 1 200000 746373183 114945773 818288863 275512286 556235952 765932487 802018780 188949726 468071953 820186183 992540472 761979358 692654417 199624066 564047436 414438039 244215074 975687005 25557598 696121044 58454783 96320065 3557616 990588952 429672232 879295946 498493922 41206787 8551770...
output:
419371679744000000
result:
ok single line: '419371679744000000'
Test #13:
score: 0
Accepted
time: 144ms
memory: 64340kb
input:
1 1000000 1 333333 957654956 646187352 32899023 624935611 756377866 513583786 905404958 299856689 262293123 13222651 887912710 988179210 864221956 36851939 35872851 356248118 601102172 28640073 748096283 552325542 838190137 74582755 522519128 5489111 855603927 255074671 662348110 44410921 539299718 ...
output:
637720407461330944
result:
ok single line: '637720407461330944'
Test #14:
score: 0
Accepted
time: 166ms
memory: 65276kb
input:
1 1000000 1 100000 95802861 952997330 711605776 174525727 306892247 741863675 46021991 357498288 635936820 39501859 456735950 545614341 152055290 49134379 266439448 517291936 440002459 530831670 616363499 989896411 76630557 775024208 34267835 292229965 925004101 759445579 858250795 356483909 1790849...
output:
419325961830400000
result:
ok single line: '419325961830400000'
Test #15:
score: 0
Accepted
time: 173ms
memory: 65508kb
input:
1 1000000 1 10000 640501582 367993241 735568655 87703364 653604624 655420338 931702132 938925121 554188512 604433243 714273063 420770802 71972891 870176648 103236889 162744478 912406829 714374382 712887046 880654297 722443445 746358911 444847764 783741325 362338620 375615984 20917607 685364863 83542...
output:
622924091300511744
result:
ok single line: '622924091300511744'
Test #16:
score: 0
Accepted
time: 184ms
memory: 65728kb
input:
1 1000000 1 1000 455196270 190484700 808804745 908100829 819541515 112822048 936976800 53291764 191542138 243481855 402616029 446442565 16167062 582520745 136577853 682696160 102121746 745488795 158873348 717288213 966019838 52547760 353555063 915506282 242599804 724902341 708882718 284942673 268915...
output:
521821346594816000
result:
ok single line: '521821346594816000'
Test #17:
score: 0
Accepted
time: 188ms
memory: 65772kb
input:
1 1000000 1 100 702799009 137196927 741616788 647171982 931344198 867588930 135480421 84575067 496306650 156599631 556286845 421906456 593318872 980772659 647787437 349834561 273163648 851803610 422635741 533495161 608213346 284846434 187767176 493865935 319569940 511511437 598022042 973212363 74279...
output:
296340288018841600
result:
ok single line: '296340288018841600'
Test #18:
score: 0
Accepted
time: 261ms
memory: 66316kb
input:
1 1000000 1 10 141443301 806352113 434088354 130437916 114823256 581542363 982820128 983006032 816808663 825544559 1 10 235698954 499936207 266837616 680474761 106480151 855186371 165993290 682305503 857741045 642102816 1 10 974022092 451800527 986368820 816661093 168532188 437905107 19261794 258967...
output:
20480
result:
ok single line: '20480'
Test #19:
score: 0
Accepted
time: 276ms
memory: 71004kb
input:
1 1000000 1 3 749226366 438769961 563276184 1 3 402990250 193556585 454133298 1 3 976667277 719206152 288131384 1 3 3958767 845880452 837087183 1 3 881298475 692087656 495758669 1 3 196675867 346680393 663820113 1 3 23487045 365426061 671605098 1 3 339028314 637314620 76939449 1 3 426002043 45152240...
output:
96
result:
ok single line: '96'
Extra Test:
score: 0
Extra Test Passed