QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#688991 | #8333. Gift | adivse# | AC ✓ | 34ms | 14024kb | C++20 | 1.4kb | 2024-10-30 14:44:02 | 2024-10-30 14:44:04 |
Judging History
answer
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N = 100005;
const int inf = 1e9;
int n;
int ans;
int rd[N];
int tmp[N];
bitset<N>flag;
int num3, num4;
queue<int>q;
vector<int>to[N];
struct edge {
int x, y;
}e[N];
vector<edge>ee;
signed main() {
ios::sync_with_stdio(false),cin.tie(0);
cin >> n;
for (int i = 1; i <= n; ++i) {
int x, y;
cin >> x >> y;
e[i].x = x; e[i].y = y;
to[x].push_back(y);
to[y].push_back(x);
rd[x]++; rd[y]++;
}
for (int i = 1; i <= n; ++i) {
if (rd[i] <= 3) num3++;
else if (rd[i] <= 4) num4++;
}
for (int i = 1; i <= n; ++i) tmp[i] = rd[i];
for (int i = 1; i <= n; ++i) {
if (tmp[i] == 1) {
q.push(i);
flag[i] = 1;
}
}
while (!q.empty()) {
int u = q.front(); q.pop();
for (auto v : to[u]) {
if (--tmp[v] == 1) {
q.push(v);
flag[v] = 1;
}
}
}
for (int i = 1; i <= n; ++i) {
if (!flag[e[i].x] && !flag[e[i].y]) {
ee.push_back(e[i]);
}
}
for (edge e : ee) {
if (rd[e.x] == 4) {num3++; num4--;}
if (rd[e.y] == 4) {num3++; num4--;}
if (rd[e.x] == 5) {num4++;}
if (rd[e.y] == 5) {num4++;}
if (num3 + num4 == n) ans += num3;
if (rd[e.x] == 4) {num3--; num4++;}
if (rd[e.y] == 4) {num3--; num4++;}
if (rd[e.x] == 5) {num4--;}
if (rd[e.y] == 5) {num4--;}
}
cout << ans << endl;
return 0;
}
/*
0 0 0 1 2 3
*/
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5608kb
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: 5708kb
input:
3 1 3 3 2 2 1
output:
9
result:
ok 1 number(s): "9"
Test #3:
score: 0
Accepted
time: 0ms
memory: 6108kb
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: 17ms
memory: 14024kb
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: 32ms
memory: 12944kb
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: 7ms
memory: 8368kb
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: 15ms
memory: 8564kb
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: 16ms
memory: 9944kb
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: 15ms
memory: 9436kb
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: 16ms
memory: 8572kb
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: 27ms
memory: 13148kb
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: 27ms
memory: 12892kb
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: 13004kb
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: 16ms
memory: 12996kb
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: 26ms
memory: 12936kb
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