QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#296482 | #7860. Graph of Maximum Degree 3 | ucup-team1766 | WA | 64ms | 12204kb | C++14 | 2.2kb | 2024-01-03 05:19:00 | 2024-01-03 05:19:01 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 998244353;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m;
cin >> n >> m;
vector<pair<int, int>> graph[n];
for (int i = 0; i < m; i++) {
int u, v, c;
cin >> u >> v >> c;
graph[--u].push_back({--v, c});
graph[v].push_back({u, c});
}
map<int, int> match;
for (int i = 0; i < n; i++) {
set<int> seen;
for (pair<int, int> e : graph[i]) {
if (seen.count(e.first) && i < e.first) {
match[i] = e.first;
}
seen.insert(e.first);
}
}
long long res = n + match.size();
long long fours1 = 0;
for (pair<int, int> p : match) {
int n1 = -1;
int c1 = -1;
for (pair<int, int> e : graph[p.first]) {
if (e.first != p.second) {
n1 = e.first;
c1 = e.second;
}
}
int n2 = -1;
int c2 = -1;
for (pair<int, int> e : graph[p.second]) {
if (e.first != p.first) {
n2 = e.first;
c2 = e.second;
}
}
if (n1 != -1 && n2 != -1) {
if (n1 == n2) {
if (c1 != c2) {
res++;
}
} else {
if (match[min(n1, n2)] == max(n1, n2) && c1 != c2) {
fours1++;
}
}
}
}
long long fours2 = 0;
for (int u = 0; u < n; u++) {
set<int> comp;
comp.insert(u);
for (pair<int, int> e : graph[u]) {
comp.insert(e.first);
}
if (comp.size() == 4) {
int cnt[] = {0, 0};
for (int v : comp) {
for (pair<int, int> e : graph[v]) {
if (comp.count(e.first)) {
cnt[e.second]++;
}
}
}
if (cnt[0] == 6 && cnt[1] == 6) {
fours2++;
}
}
}
cout << (res + fours1 / 2 + fours2 / 4) % MOD << endl;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3476kb
input:
3 4 1 2 0 1 3 1 2 3 0 2 3 1
output:
5
result:
ok 1 number(s): "5"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3432kb
input:
4 6 1 2 0 2 3 0 3 4 0 1 4 1 2 4 1 1 3 1
output:
5
result:
ok 1 number(s): "5"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3540kb
input:
20 28 9 6 1 9 6 0 3 8 0 8 4 0 3 8 1 3 4 1 2 13 0 13 1 0 19 1 0 2 1 1 2 19 1 13 19 1 14 15 1 14 15 0 7 12 0 12 17 0 20 17 0 7 17 1 7 20 1 12 20 1 16 18 0 18 10 0 5 10 0 16 10 1 16 5 1 18 5 1 4 6 0 9 11 0
output:
27
result:
ok 1 number(s): "27"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
100 150 93 23 0 23 81 0 76 81 0 93 81 1 93 76 1 23 76 1 100 65 0 65 56 0 19 56 0 100 56 1 100 19 1 65 19 1 2 98 0 2 98 1 26 63 0 63 90 0 26 63 1 26 90 1 6 11 0 11 67 0 6 11 1 6 67 1 37 89 0 89 64 0 25 64 0 37 64 1 37 25 1 89 25 1 84 10 0 10 29 0 75 29 0 84 29 1 84 75 1 10 75 1 7 70 1 7 70 0 28 92 0 ...
output:
141
result:
ok 1 number(s): "141"
Test #5:
score: 0
Accepted
time: 58ms
memory: 11076kb
input:
100000 133680 36843 86625 0 86625 63051 0 35524 63051 0 36843 63051 1 36843 35524 1 86625 35524 1 55797 82715 0 55797 82715 1 70147 35104 0 35104 91732 0 70147 35104 1 70147 91732 1 94917 70395 0 70395 68250 0 24100 68250 0 94917 68250 1 94917 24100 1 70395 24100 1 83033 18450 1 83033 18450 0 34462 ...
output:
144604
result:
ok 1 number(s): "144604"
Test #6:
score: 0
Accepted
time: 56ms
memory: 10980kb
input:
100000 133388 86620 74346 0 74346 19047 0 54911 19047 0 86620 19047 1 86620 54911 1 74346 54911 1 23715 93094 0 93094 91208 0 63189 91208 0 23715 91208 1 23715 63189 1 93094 63189 1 99337 41426 1 99337 41426 0 83742 45546 0 45546 73862 0 83742 45546 1 83742 73862 1 85256 2812 0 2812 59368 0 85918 59...
output:
144348
result:
ok 1 number(s): "144348"
Test #7:
score: 0
Accepted
time: 61ms
memory: 12204kb
input:
100000 150000 86541 24385 0 24385 75745 0 52353 75745 0 86541 75745 1 86541 52353 1 24385 52353 1 89075 78015 0 89075 78015 1 52519 74846 0 74846 12045 0 73265 12045 0 52519 12045 1 52519 73265 1 74846 73265 1 17884 63159 0 63159 47308 0 56073 47308 0 17884 47308 1 17884 56073 1 63159 56073 1 72134 ...
output:
144639
result:
ok 1 number(s): "144639"
Test #8:
score: 0
Accepted
time: 62ms
memory: 12204kb
input:
100000 150000 91951 68612 1 91951 68612 0 18361 92673 0 92673 52678 0 86520 52678 0 18361 52678 1 18361 86520 1 92673 86520 1 58779 2421 0 58779 2421 1 66622 6461 0 6461 96943 0 66622 6461 1 66622 96943 1 27201 480 1 27201 480 0 19082 3895 0 3895 17796 0 3117 17796 0 19082 17796 1 19082 3117 1 3895 ...
output:
144471
result:
ok 1 number(s): "144471"
Test #9:
score: 0
Accepted
time: 55ms
memory: 12172kb
input:
100000 150000 43756 3552 0 3552 90269 0 43756 3552 1 43756 90269 1 11104 36935 1 11104 36935 0 11648 5480 0 5480 45320 0 11648 5480 1 11648 45320 1 19216 85746 0 19216 85746 1 68825 11173 0 11173 43155 0 68825 11173 1 68825 43155 1 27349 75259 0 27349 75259 1 1704 24478 0 24478 5980 0 1704 24478 1 1...
output:
144217
result:
ok 1 number(s): "144217"
Test #10:
score: 0
Accepted
time: 58ms
memory: 12188kb
input:
99999 149998 51151 43399 0 51151 43399 1 45978 28343 0 28343 9008 0 85724 9008 0 45978 9008 1 45978 85724 1 28343 85724 1 79446 12915 0 12915 65925 0 28869 65925 0 79446 65925 1 79446 28869 1 12915 28869 1 82642 95556 0 95556 68817 0 68334 68817 0 82642 68817 1 82642 68334 1 95556 68334 1 61212 7638...
output:
144219
result:
ok 1 number(s): "144219"
Test #11:
score: 0
Accepted
time: 61ms
memory: 12196kb
input:
100000 149999 26736 28785 0 28785 37945 0 26736 28785 1 26736 37945 1 1240 74368 0 74368 45022 0 1240 74368 1 1240 45022 1 40673 1276 0 1276 56395 0 40673 1276 1 40673 56395 1 35181 63341 0 63341 35131 0 60120 35131 0 35181 35131 1 35181 60120 1 63341 60120 1 99363 36973 0 99363 36973 1 85717 77683 ...
output:
144380
result:
ok 1 number(s): "144380"
Test #12:
score: 0
Accepted
time: 61ms
memory: 12204kb
input:
100000 150000 63695 11044 0 11044 34978 0 56531 34978 0 63695 34978 1 63695 56531 1 11044 56531 1 72139 3715 0 3715 21024 0 96696 21024 0 72139 21024 1 72139 96696 1 3715 96696 1 54670 49014 0 54670 49014 1 7670 61055 0 61055 38409 0 7670 61055 1 7670 38409 1 83399 50676 0 50676 98893 0 60069 98893 ...
output:
144559
result:
ok 1 number(s): "144559"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
1 0
output:
1
result:
ok 1 number(s): "1"
Test #14:
score: 0
Accepted
time: 4ms
memory: 5768kb
input:
100000 0
output:
100000
result:
ok 1 number(s): "100000"
Test #15:
score: 0
Accepted
time: 64ms
memory: 10460kb
input:
100000 150000 95066 31960 0 31960 89758 0 10935 89758 0 95066 89758 1 95066 10935 1 31960 10935 1 48016 97823 0 97823 10871 0 23454 10871 0 48016 10871 1 48016 23454 1 97823 23454 1 73749 35525 0 35525 54232 0 42182 54232 0 73749 54232 1 73749 42182 1 35525 42182 1 75405 71341 0 71341 70032 0 3284 7...
output:
125000
result:
ok 1 number(s): "125000"
Test #16:
score: 0
Accepted
time: 0ms
memory: 3372kb
input:
4 6 1 2 0 1 2 1 1 3 0 2 4 1 3 4 0 3 4 1
output:
7
result:
ok 1 number(s): "7"
Test #17:
score: -100
Wrong Answer
time: 49ms
memory: 10516kb
input:
99998 115940 40840 40839 0 28249 28248 0 24785 24783 0 36536 36534 1 71904 71901 1 62023 62021 0 34737 34740 1 18430 18434 0 27506 27505 1 4665 4664 1 36578 36577 1 99311 99314 1 43484 43482 0 26457 26459 1 99698 99695 0 10170 10172 1 98176 98179 1 47786 47785 1 56529 56531 1 86896 86895 1 78204 782...
output:
104921
result:
wrong answer 1st numbers differ - expected: '104913', found: '104921'