QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#608892#9349. Exchanging GiftsYour-SunTL 780ms13816kbC++201.6kb2024-10-04 08:51:052024-10-04 08:51:06

Judging History

你现在查看的是最新测评结果

  • [2024-10-04 08:51:06]
  • 评测
  • 测评结果:TL
  • 用时:780ms
  • 内存:13816kb
  • [2024-10-04 08:51:05]
  • 提交

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...

output:


result: