QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #722729 | #8760. 不等式 | Vocal# | WA | 2ms | 11912kb | C++23 | 1.9kb | 2024-11-07 20:03:36 | 2024-11-07 20:03:37 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<int>q[200010];
pair<int,int>b[200010];
int vis[200010];
int d[200010];
int bj = 1;
int x[200010],y[200010],z[200010];
int dfs(int x) {
if( !bj )return 0;
if( q[x].size() == 0 ) {
b[x].first = 1;
return 1;
}
if( b[x].first ) {
return b[x].first+b[x].second;
}
int res = 0;
for(int i = 0;i < q[x].size(); ++i) {
if( vis[q[x][i]] )bj = 0;
vis[q[x][i]] = 1;
res = dfs(q[x][i]);
if( res > b[x].first ) {
b[x].second = b[x].first;
b[x].first = res;
}
else if( res > b[x].second )b[x].second = res;
vis[q[x][i]] = 0;
if( b[x].first+b[x].second > 1000000000 ) {
bj = 0;
return 0;
}
}
return b[x].first+b[x].second;
}
signed main() {
int n,m;
cin >> n >>m;
for(int i = 1;i <= m; ++i) {
int u,v1,v2;
cin >> u >> v1 >> v2;
x[i] = u;
y[i] = v1;
z[i] = v2;
q[u].push_back(v1);
q[u].push_back(v2);
d[v1]++;
d[v2]++;
}
int ans = 0;
for(int i = 1;i <= n; ++i) {
if( !d[i] ) {
vis[i] = 1;
dfs(i);
vis[i] = 0;
}
}
for(int i = 1;i <= n; ++i) {
ans += b[i].first+b[i].second,bj = min(bj,b[i].first);
if( b[x[i]].first+b[x[i]].second < b[y[i]].first+b[y[i]].second+ b[z[i]].first+b[z[i]].second) {
bj = 0;
break;
}
if( ans > 1000000000 ) {
bj = 0;
break;
}
}
if( bj && ans <= 1000000000 )cout << ans <<endl;
else cout << -1 << endl;
return 0;
}
// 13 10
// 1 2 3
// 1 3 4
// 2 5 6
// 3 7 8
// 5 10 11
// 6 10 11
// 7 10 11
// 8 10 11
// 4 8 9
// 12 9 13
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 9860kb
input:
3 1 1 2 2
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 2ms
memory: 9724kb
input:
3 1 1 2 3
output:
4
result:
ok 1 number(s): "4"
Test #3:
score: 0
Accepted
time: 2ms
memory: 9788kb
input:
3 1 1 2 2
output:
4
result:
ok 1 number(s): "4"
Test #4:
score: 0
Accepted
time: 0ms
memory: 9868kb
input:
3 1 1 2 2
output:
4
result:
ok 1 number(s): "4"
Test #5:
score: 0
Accepted
time: 0ms
memory: 9724kb
input:
3 1 1 2 2
output:
4
result:
ok 1 number(s): "4"
Test #6:
score: 0
Accepted
time: 2ms
memory: 9780kb
input:
5 1 1 2 2
output:
6
result:
ok 1 number(s): "6"
Test #7:
score: 0
Accepted
time: 0ms
memory: 9848kb
input:
5 1 1 2 2
output:
6
result:
ok 1 number(s): "6"
Test #8:
score: 0
Accepted
time: 0ms
memory: 11912kb
input:
5 1 1 2 2
output:
6
result:
ok 1 number(s): "6"
Test #9:
score: 0
Accepted
time: 1ms
memory: 9844kb
input:
5 1 1 2 3
output:
6
result:
ok 1 number(s): "6"
Test #10:
score: 0
Accepted
time: 2ms
memory: 9780kb
input:
5 2 1 2 3 2 3 4
output:
8
result:
ok 1 number(s): "8"
Test #11:
score: 0
Accepted
time: 2ms
memory: 9776kb
input:
10 1 1 2 3
output:
11
result:
ok 1 number(s): "11"
Test #12:
score: 0
Accepted
time: 2ms
memory: 9788kb
input:
10 1 1 2 2
output:
11
result:
ok 1 number(s): "11"
Test #13:
score: 0
Accepted
time: 2ms
memory: 9836kb
input:
10 2 1 2 3 2 3 4
output:
13
result:
ok 1 number(s): "13"
Test #14:
score: 0
Accepted
time: 0ms
memory: 9796kb
input:
10 2 1 2 2 2 3 4
output:
14
result:
ok 1 number(s): "14"
Test #15:
score: 0
Accepted
time: 2ms
memory: 9776kb
input:
10 3 1 2 3 1 8 8 2 3 3
output:
13
result:
ok 1 number(s): "13"
Test #16:
score: 0
Accepted
time: 1ms
memory: 9840kb
input:
20 1 1 2 2
output:
21
result:
ok 1 number(s): "21"
Test #17:
score: 0
Accepted
time: 1ms
memory: 9776kb
input:
20 2 1 2 3 2 3 3
output:
23
result:
ok 1 number(s): "23"
Test #18:
score: 0
Accepted
time: 1ms
memory: 9716kb
input:
20 3 7 14 6 1 2 3 4 7 20
output:
24
result:
ok 1 number(s): "24"
Test #19:
score: 0
Accepted
time: 0ms
memory: 9720kb
input:
20 4 1 2 2 6 10 6 2 3 3 3 4 5
output:
-1
result:
ok 1 number(s): "-1"
Test #20:
score: 0
Accepted
time: 1ms
memory: 9776kb
input:
20 5 1 17 3 1 2 3 2 3 4 3 4 5 8 13 16
output:
28
result:
ok 1 number(s): "28"
Test #21:
score: 0
Accepted
time: 0ms
memory: 9796kb
input:
200 9 1 2 2 2 3 3 3 4 5 91 112 195 126 145 82 4 5 5 53 2 15 5 6 6 6 7 7
output:
318
result:
ok 1 number(s): "318"
Test #22:
score: 0
Accepted
time: 0ms
memory: 9792kb
input:
200 17 1 2 2 100 69 47 159 84 111 2 3 3 3 4 5 4 5 5 8 9 76 5 6 7 158 81 154 189 62 45 192 159 181 6 7 7 15 181 91 7 193 152 140 65 66 7 8 9 32 157 67
output:
428
result:
ok 1 number(s): "428"
Test #23:
score: 0
Accepted
time: 1ms
memory: 9788kb
input:
200 25 118 152 40 172 193 173 126 32 89 1 2 3 147 148 112 2 3 4 3 4 4 35 116 95 179 193 64 70 22 55 4 5 5 5 6 6 24 74 182 184 168 129 6 7 8 7 8 9 109 63 173 8 9 10 38 125 106 68 147 40 33 65 46 144 12 168 9 10 11 10 11 11 190 73 48
output:
835
result:
ok 1 number(s): "835"
Test #24:
score: 0
Accepted
time: 2ms
memory: 11888kb
input:
200 33 1 2 3 165 80 199 2 3 4 10 80 12 3 4 5 4 5 6 5 6 7 128 1 190 6 7 7 166 124 95 7 8 9 60 51 80 25 158 81 108 107 99 8 9 9 9 10 10 10 11 12 54 41 100 11 12 13 176 185 149 12 13 13 13 14 14 14 15 16 15 16 17 16 17 17 128 73 196 17 18 19 93 169 141 18 19 19 19 20 20 20 21 21 21 22 22 12 55 32
output:
543121
result:
ok 1 number(s): "543121"
Test #25:
score: 0
Accepted
time: 1ms
memory: 9784kb
input:
200 41 1 2 3 2 3 3 3 4 4 4 5 5 175 3 161 5 6 7 6 7 8 7 8 9 8 9 10 9 10 10 10 11 11 24 15 157 82 57 72 161 48 197 149 96 16 30 3 131 165 114 21 143 110 56 11 12 12 12 13 13 13 14 14 62 183 153 14 15 15 15 16 16 192 139 91 178 54 86 16 17 18 158 59 18 17 18 19 35 91 197 18 19 20 99 129 43 168 76 146 7...
output:
-1
result:
ok 1 number(s): "-1"
Test #26:
score: 0
Accepted
time: 1ms
memory: 9824kb
input:
2000 81 97 630 1373 398 361 536 1 2 3 2 3 4 3 4 5 1573 1392 1526 645 1562 79 1833 239 840 4 5 5 1122 972 412 5 6 7 1089 190 1311 672 1664 887 6 7 8 805 1221 1635 7 8 8 8 9 9 1001 1271 267 176 200 567 1800 762 1129 1978 1273 429 1965 155 68 295 1714 836 499 1093 465 9 10 11 10 11 11 11 12 13 12 13 14...
output:
1474361
result:
ok 1 number(s): "1474361"
Test #27:
score: 0
Accepted
time: 1ms
memory: 9876kb
input:
2000 161 594 271 957 633 1085 1384 1133 1233 916 1463 1353 621 1 2 2 514 1052 224 814 744 1837 44 195 1186 2 3 4 1272 606 1531 739 706 1827 1862 1014 834 3 4 5 4 5 5 1063 1246 1103 935 318 593 1657 93 324 583 987 1283 1258 1051 866 1187 1012 1167 1427 1825 589 5 6 7 1055 141 69 491 1545 487 739 1255...
output:
47813842
result:
ok 1 number(s): "47813842"
Test #28:
score: 0
Accepted
time: 1ms
memory: 9864kb
input:
2000 241 410 1433 1627 1489 1395 611 1 2 3 2 3 3 1553 1507 1544 3 4 4 4 5 5 1073 1318 1088 112 333 87 1322 187 439 461 1272 1516 1385 813 1044 784 954 1186 449 53 531 5 6 6 644 1277 1454 76 1249 1631 1233 992 209 310 416 447 909 227 1268 956 594 1727 1576 1567 116 1954 1245 1988 1755 1154 437 1539 1...
output:
-1
result:
ok 1 number(s): "-1"
Test #29:
score: 0
Accepted
time: 0ms
memory: 9816kb
input:
2000 321 542 97 1114 519 254 1751 1344 621 878 1701 682 1976 947 139 618 1930 986 1144 437 1803 1241 694 1316 1725 636 1886 1728 406 1435 453 530 802 1423 1575 1283 1451 64 982 536 990 123 1412 1 2 2 1013 1788 773 792 353 98 22 1024 1038 1169 1251 1780 2 3 4 573 1327 205 1575 102 474 420 717 451 84 ...
output:
12640161
result:
ok 1 number(s): "12640161"
Test #30:
score: -100
Wrong Answer
time: 0ms
memory: 9836kb
input:
2000 401 1 2 3 1302 160 543 431 1432 1771 727 1624 144 1965 1363 365 360 1 1960 483 140 110 169 745 1102 608 917 1278 1258 1883 734 1855 748 1859 2 3 3 68 741 1342 1762 323 124 1686 1481 57 515 1497 699 1283 1923 1461 135 870 1705 1715 579 700 139 607 1680 58 550 1717 774 763 589 142 883 701 1982 83...
output:
52876268
result:
wrong answer 1st numbers differ - expected: '52876264', found: '52876268'