QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#608892 | #9349. Exchanging Gifts | Your-Sun | TL | 780ms | 13816kb | C++20 | 1.6kb | 2024-10-04 08:51:05 | 2024-10-04 08:51:06 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define endl '\n'
void solve()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int n;
cin>>n;
vector<vector<ll>> a(n+1);
vector<pii> b(n+1);
for(int i=1;i<=n;i++)
{
ll op;
cin>>op;
if(op==1)
{
ll m;
cin>>m;
a[i].resize(m);
for(int j=0;j<m;j++)
cin>>a[i][j];
}
else // op=2
{
int x,y;
cin>>x>>y;
b[i]=make_pair(x,y);
}
}
// cerr<<"middle1\n";
// for(auto x:a[1])
// cerr<<x<<' ';
// cerr<<endl;
map<ll,ll> mp;
if(a[n].size())
for(auto x:a[n])
mp[x]++;
else
{
for(int i=1;i<n;i++)
{
if(!a[i].size())
continue;
vector<ll> c(n+1);
c[i]=1;
for(int j=i+1;j<=n;j++)
{
auto [x,y]=b[j];
c[j]=c[x]+c[y];
}
if(!c[n])
continue;
for(auto x:a[i])
mp[x]+=c[n];
}
}
// cal ????
// cerr<<"middle2\n";
ll res=0, mx=0, total=0;
for(auto [x,y]:mp)
mx=max(mx,y), total+=y;
if(mx<=total-mx)
res=total;
else
res=2*(total-mx);
cout<<res<<endl;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int T;
cin>>T;
while(T--)
solve();
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3528kb
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: 193ms
memory: 3556kb
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: 196ms
memory: 3688kb
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: 204ms
memory: 4700kb
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: 292ms
memory: 12160kb
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: 469ms
memory: 13816kb
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: 780ms
memory: 13140kb
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: -100
Time Limit Exceeded
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...