QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#712740#8333. Gift13728129942AC ✓103ms14756kbC++201.4kb2024-11-05 16:52:572024-11-05 16:52:58

Judging History

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

  • [2024-11-05 16:52:58]
  • 评测
  • 测评结果:AC
  • 用时:103ms
  • 内存:14756kb
  • [2024-11-05 16:52:57]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
vector<int> v[N];
int du[N],du1[N];
void solve() {
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        int a,b;cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
        du[a]++,du[b]++;
        du1[a]++,du1[b]++;
    }
        queue<int> q;
        int sum=0;
    set<int> S1;
    for(int i=1;i<=n;i++){
        if(du1[i]==1){
            q.push(i);                }
        if(du1[i]>=4)    sum+=1;
        if(du1[i]==5)    S1.insert(i);
    }
        while(q.size()){
        auto now=q.front();q.pop();
                for(auto u:v[now]){
            if(du1[u]==1)  continue;
            du1[u]--;
            if(du1[u]==1){
                q.push(u);
            }
        }
    }
    set<int> S;
    for(int i=1;i<=n;i++)
        if(du1[i]!=1)S.insert(i);
    ll ans=0;
    for(auto a:S){
        for(auto b:v[a]){
            if(S.count(b)==0)    continue;
            if(S1.size()-S1.count(a)-S1.count(b)!=0)    continue;
            ans+=n-sum;
            if(du[a]==4)    ans++;
            if(du[b]==4)    ans++;
        }
    }
    cout<<ans/2<<endl;
    }
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
//    cin >> T;
   // cout << fixed << setprecision(20);
    while (T--) {
        solve();
    }
    return 0;
}

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3628kb

input:

6
1 2
1 3
1 4
1 5
1 6
2 3

output:

10

result:

ok 1 number(s): "10"

Test #2:

score: 0
Accepted
time: 1ms
memory: 3792kb

input:

3
1 3
3 2
2 1

output:

9

result:

ok 1 number(s): "9"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3748kb

input:

2332
1648 909
1676 2122
1644 1981
1106 1131
1785 239
223 618
335 1662
424 1775
889 1684
1589 52
1406 1747
1600 302
790 2056
1742 464
1706 541
1145 779
2316 833
1645 1439
859 438
1337 136
746 1565
436 1730
2079 2145
1583 1940
917 1549
1863 507
1266 367
1890 2230
13 2113
492 2109
120 1122
815 1111
134...

output:

5438224

result:

ok 1 number(s): "5438224"

Test #4:

score: 0
Accepted
time: 103ms
memory: 14756kb

input:

100000
46198 33056
80285 88339
88963 925
43203 66233
13618 35880
19864 76475
90021 73072
3202 63653
41571 83067
22067 98768
10753 16653
32856 85797
3483 2064
46659 9486
23290 82179
97966 23617
81566 7334
81774 76138
10959 75816
93471 12058
97260 66262
85541 78476
67864 87220
8607 52245
38957 67603
7...

output:

10000000000

result:

ok 1 number(s): "10000000000"

Test #5:

score: 0
Accepted
time: 61ms
memory: 12160kb

input:

100000
54772 14057
70680 93042
84913 63248
79360 97774
84190 60881
31137 29439
99037 81117
38579 32074
31206 19912
70774 23067
60717 79586
83847 43306
55351 50174
32566 70092
22736 92279
55916 20029
41571 63309
33143 65579
35033 3869
50038 4275
59533 25348
53092 32698
27604 14678
6802 18226
23173 96...

output:

5017400000

result:

ok 1 number(s): "5017400000"

Test #6:

score: 0
Accepted
time: 15ms
memory: 6956kb

input:

50000
26768 20197
5956 49805
44024 45008
29783 4843
7173 42904
36329 3666
1258 35410
1245 42591
41226 20145
41177 25916
38397 36431
3822 43842
414 31694
28969 33316
47036 42639
5433 1631
26813 16959
17557 18806
45146 10231
26867 24805
4416 45505
44772 32136
26263 17264
43426 20507
26630 4199
9781 89...

output:

94055

result:

ok 1 number(s): "94055"

Test #7:

score: 0
Accepted
time: 10ms
memory: 6836kb

input:

50000
17715 45957
32674 24013
11618 34470
40375 26273
42845 13128
47455 22000
32874 30876
17491 31661
34844 19762
9072 37619
36110 709
268 34175
4270 20690
29515 33513
27912 43001
45583 31336
47547 28782
26922 36614
28304 10847
34444 24189
22768 40293
20188 44360
15389 17250
1073 12635
2478 47836
13...

output:

8051734

result:

ok 1 number(s): "8051734"

Test #8:

score: 0
Accepted
time: 14ms
memory: 6768kb

input:

50000
37455 39098
3151 6272
5096 39790
49906 13081
31622 31592
39120 11585
15349 45507
10760 45706
28023 41368
2327 29590
41990 47577
29250 11516
6810 9343
32121 42608
9553 4051
8790 3141
47114 45057
20325 1150
16016 28877
29716 6021
37777 41072
10612 27253
30459 933
29861 21955
49824 3068
17709 270...

output:

92740

result:

ok 1 number(s): "92740"

Test #9:

score: 0
Accepted
time: 9ms
memory: 6996kb

input:

50000
45571 37975
37274 7584
8276 23675
19496 33814
44225 8331
5709 10694
35506 34740
26328 48062
6085 4427
32680 40409
34161 34842
24200 48199
6831 13256
11261 9734
36423 35721
31037 31766
13399 1942
8062 49588
33071 34851
29051 34723
37974 8227
49945 3621
21863 21924
5665 23743
25046 6591
12174 37...

output:

90984

result:

ok 1 number(s): "90984"

Test #10:

score: 0
Accepted
time: 10ms
memory: 6768kb

input:

50000
35332 25321
25253 26808
1825 13008
42512 12213
42348 46975
15945 10783
37617 25404
12439 31594
28739 24025
21314 26502
3686 22867
19502 47228
15246 7358
35904 4586
5286 15305
28693 13776
44276 7562
27838 5500
40919 52
41478 9675
15676 32415
41353 12056
8301 33451
37563 9459
22381 2826
34996 30...

output:

91952

result:

ok 1 number(s): "91952"

Test #11:

score: 0
Accepted
time: 30ms
memory: 10296kb

input:

100000
5728 9676
70005 86016
43967 6069
25998 15992
25120 46215
71280 3926
50960 33180
76103 91653
39019 53916
31 75541
35484 59797
37091 77981
25183 81534
74314 5751
20419 13475
90063 53064
30839 82393
1073 25122
411 54274
54359 70033
98701 10404
26563 65104
52630 57315
90442 20265
42089 11579
7252...

output:

188242

result:

ok 1 number(s): "188242"

Test #12:

score: 0
Accepted
time: 30ms
memory: 9964kb

input:

100000
55116 18295
96650 80557
4329 50722
1313 76368
37587 25825
78537 18103
406 68671
43420 28393
80913 24601
87683 96542
694 11917
63199 34678
95157 80210
97679 9115
63390 92793
51246 50937
19788 11356
31360 1607
66115 73059
64415 38370
76283 57331
69105 62126
19137 88106
62951 78941
65947 67688
1...

output:

91568

result:

ok 1 number(s): "91568"

Test #13:

score: 0
Accepted
time: 34ms
memory: 10260kb

input:

100000
50883 5999
18393 12126
15334 91408
26392 76076
62384 55943
17693 8898
2559 35077
40756 62967
98202 86230
83949 19932
93158 85510
88663 12650
59846 99904
68413 56736
48738 11679
75726 10843
84088 73780
39309 76757
12359 47501
12053 92575
93789 5454
88405 8870
88404 82684
68204 7531
56193 6902
...

output:

871424097

result:

ok 1 number(s): "871424097"

Test #14:

score: 0
Accepted
time: 26ms
memory: 10224kb

input:

100000
27780 67107
53072 40333
54627 40033
18181 70192
35779 96307
60226 65350
58800 16492
36355 9164
14772 30265
57612 51460
25930 51526
65289 32689
14113 76118
98134 15045
15843 85609
13703 10951
36770 150
71969 59581
34799 82901
59566 35128
2207 24992
63359 83776
5691 40927
90796 76499
86070 8515...

output:

91321

result:

ok 1 number(s): "91321"

Test #15:

score: 0
Accepted
time: 31ms
memory: 9956kb

input:

100000
85137 23757
36555 12897
94235 26110
54855 82870
71976 42445
27780 91475
42701 65921
24419 81582
90491 10676
48481 499
97884 16017
31986 29961
45841 42903
24099 12773
46256 21809
41322 96979
1452 14537
12450 8054
34128 29501
13209 17651
58310 14198
51601 55782
8944 2603
38035 47152
68136 90471...

output:

92070

result:

ok 1 number(s): "92070"

Extra Test:

score: 0
Extra Test Passed