QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #439723 | #8760. 不等式 | ship2077 | AC ✓ | 38ms | 18760kb | C++14 | 987b | 2024-06-12 16:44:21 | 2024-06-12 16:44:23 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
constexpr int M=2e5+5,lim=1e9;
vector<int>g[M];int n,m,ans;
int a[M],x[M],y[M],z[M],cnt[M],deg[M];
int read(){
int x=0;char ch=getchar();
while (!isdigit(ch)) ch=getchar();
while (isdigit(ch)) x=x*10+ch-48,ch=getchar();
return x;
}
int main(){
n=read();m=read();
for (int i=1;i<=n;i++) a[i]=1;
for (int i=1;i<=m;i++){
z[i]=read();x[i]=read();y[i]=read();
g[x[i]].emplace_back(i);
g[y[i]].emplace_back(i);
deg[z[i]]++;cnt[i]=2;
} queue<int>q;
for (int i=1;i<=n;i++)
if (!deg[i])
q.emplace(i);
while (!q.empty()){
int p=q.front();q.pop();
for (auto i:g[p])
if (!--cnt[i]){
if (a[x[i]]+a[y[i]]>lim) return puts("-1"),0;
a[z[i]]=max(a[z[i]],a[x[i]]+a[y[i]]);
if (!--deg[z[i]]) q.emplace(z[i]);
}
}
for (int i=1;i<=n;i++)
if (deg[i]) return puts("-1"),0;
for (int i=1;i<=n;i++)
if ((ans+=a[i])>lim)
return puts("-1"),0;
printf("%d\n",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 12016kb
input:
3 1 1 2 2
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 3ms
memory: 11928kb
input:
3 1 1 2 3
output:
4
result:
ok 1 number(s): "4"
Test #3:
score: 0
Accepted
time: 0ms
memory: 12212kb
input:
3 1 1 2 2
output:
4
result:
ok 1 number(s): "4"
Test #4:
score: 0
Accepted
time: 0ms
memory: 11408kb
input:
3 1 1 2 2
output:
4
result:
ok 1 number(s): "4"
Test #5:
score: 0
Accepted
time: 2ms
memory: 12808kb
input:
3 1 1 2 2
output:
4
result:
ok 1 number(s): "4"
Test #6:
score: 0
Accepted
time: 2ms
memory: 11284kb
input:
5 1 1 2 2
output:
6
result:
ok 1 number(s): "6"
Test #7:
score: 0
Accepted
time: 2ms
memory: 11552kb
input:
5 1 1 2 2
output:
6
result:
ok 1 number(s): "6"
Test #8:
score: 0
Accepted
time: 2ms
memory: 12508kb
input:
5 1 1 2 2
output:
6
result:
ok 1 number(s): "6"
Test #9:
score: 0
Accepted
time: 2ms
memory: 12288kb
input:
5 1 1 2 3
output:
6
result:
ok 1 number(s): "6"
Test #10:
score: 0
Accepted
time: 0ms
memory: 11608kb
input:
5 2 1 2 3 2 3 4
output:
8
result:
ok 1 number(s): "8"
Test #11:
score: 0
Accepted
time: 0ms
memory: 12672kb
input:
10 1 1 2 3
output:
11
result:
ok 1 number(s): "11"
Test #12:
score: 0
Accepted
time: 2ms
memory: 12236kb
input:
10 1 1 2 2
output:
11
result:
ok 1 number(s): "11"
Test #13:
score: 0
Accepted
time: 3ms
memory: 12092kb
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: 11472kb
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: 11444kb
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: 3ms
memory: 12476kb
input:
20 1 1 2 2
output:
21
result:
ok 1 number(s): "21"
Test #17:
score: 0
Accepted
time: 2ms
memory: 12060kb
input:
20 2 1 2 3 2 3 3
output:
23
result:
ok 1 number(s): "23"
Test #18:
score: 0
Accepted
time: 2ms
memory: 11460kb
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: 12024kb
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: 0ms
memory: 11604kb
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: 2ms
memory: 12260kb
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: 3ms
memory: 12608kb
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: 3ms
memory: 11964kb
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: 0ms
memory: 12348kb
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: 0ms
memory: 11420kb
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: 2ms
memory: 12332kb
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: 2ms
memory: 11592kb
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: 2ms
memory: 12360kb
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: 2ms
memory: 11316kb
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: 0
Accepted
time: 2ms
memory: 11932kb
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:
52876264
result:
ok 1 number(s): "52876264"
Test #31:
score: 0
Accepted
time: 0ms
memory: 12564kb
input:
20000 801 5877 15165 15028 11576 11516 11520 16218 6592 12411 15348 8674 8282 9862 8401 4574 13463 5479 18405 45 16626 4656 7030 15740 1491 10040 14135 7870 442 13386 17115 17476 7163 4310 12916 18260 6051 3696 13552 2782 11458 10057 4453 7852 7373 8617 3562 13122 7383 1032 7508 14804 19557 11987 97...
output:
480272
result:
ok 1 number(s): "480272"
Test #32:
score: 0
Accepted
time: 0ms
memory: 12600kb
input:
20000 1601 3314 8694 954 267 12497 3314 11554 221 11833 14065 12863 18562 3742 16399 16058 12947 9367 19342 3006 1650 10622 18442 18553 17025 14309 10788 11772 17294 10946 13485 14863 4849 15616 3128 10007 7911 4337 4902 10117 3193 16846 10501 4601 19228 492 12349 18737 9543 2995 88 3661 5506 10327 ...
output:
489842040
result:
ok 1 number(s): "489842040"
Test #33:
score: 0
Accepted
time: 0ms
memory: 12500kb
input:
20000 2401 7563 8689 19481 15026 11082 13309 6006 2484 14129 19762 9195 13823 14950 11552 11417 17407 5792 19300 19924 15163 9770 4298 12092 2068 5837 14172 19144 15020 9199 8479 13355 12613 3860 14407 19824 3598 12389 12802 19721 19454 15014 2253 11530 13152 7460 11322 8123 17292 9216 11229 2479 50...
output:
-1
result:
ok 1 number(s): "-1"
Test #34:
score: 0
Accepted
time: 0ms
memory: 12840kb
input:
20000 3201 3674 9684 1181 17713 17983 16470 11780 16973 9259 8462 15968 14273 6766 11379 16472 18288 17885 19261 15526 9234 1499 667 5543 9727 18011 13814 9253 15131 192 13892 3719 1207 16935 2827 7890 13382 16363 6478 3034 6858 15331 5223 1496 13505 4922 13416 13515 16369 1259 17799 14319 6539 1852...
output:
-1
result:
ok 1 number(s): "-1"
Test #35:
score: 0
Accepted
time: 3ms
memory: 12648kb
input:
20000 4001 16859 17976 17850 8548 15132 16615 3474 14208 1421 2640 12590 3877 10026 7990 8750 6738 8990 170 14817 960 5083 12274 3907 12142 1136 12667 14552 6488 11072 7459 10272 1800 13863 19975 12688 4873 7459 10350 464 3705 11442 7911 7126 10150 11031 19880 1883 14689 12673 16400 666 321 15061 61...
output:
75048290
result:
ok 1 number(s): "75048290"
Test #36:
score: 0
Accepted
time: 3ms
memory: 13968kb
input:
200000 8001 196804 144294 145535 82700 182224 2512 118718 85283 144777 194915 79055 27427 90530 132908 74308 146670 11981 172278 111236 91866 126548 112232 194588 17173 68948 146049 108664 197864 86800 72511 138178 98870 36262 25019 145381 63352 133426 17859 155825 198286 7901 107986 85706 177110 12...
output:
80398603
result:
ok 1 number(s): "80398603"
Test #37:
score: 0
Accepted
time: 8ms
memory: 14688kb
input:
200000 16001 173945 42883 29859 169651 88591 134713 138079 44779 178362 7187 176734 178824 161452 29391 39495 103057 82062 193884 54000 63670 143363 22943 191214 157212 8675 9533 150661 117446 196725 4933 129537 44472 196226 114048 26002 120575 154258 199449 120733 30197 39924 82584 180395 103765 14...
output:
573242354
result:
ok 1 number(s): "573242354"
Test #38:
score: 0
Accepted
time: 6ms
memory: 15204kb
input:
200000 24001 193002 130306 117271 3086 10064 168046 46828 145491 179203 193501 38339 55317 5714 67382 99492 49793 4018 30537 26781 68176 104015 49601 174520 91052 34871 17171 120609 146590 138563 118488 78930 86279 84543 192977 81748 71818 174107 193972 144514 8573 26143 13563 39872 120397 128208 10...
output:
-1
result:
ok 1 number(s): "-1"
Test #39:
score: 0
Accepted
time: 6ms
memory: 14920kb
input:
200000 32001 163798 41523 190015 151157 179243 8296 184989 72027 146885 20736 185133 188416 41590 17172 13988 99543 41782 108808 135503 54382 143182 134629 70069 138488 24182 98865 131312 138164 162449 1629 146538 59740 53989 26220 180290 185259 93909 41688 54008 34214 132103 152013 19434 92074 1735...
output:
-1
result:
ok 1 number(s): "-1"
Test #40:
score: 0
Accepted
time: 38ms
memory: 18760kb
input:
200000 200000 15884 195344 81993 16509 52254 99664 4857 107216 153434 58393 145718 106534 38495 193301 171396 185604 171050 140238 140319 62736 54045 92691 85811 78087 70450 6086 75930 25945 17914 189984 71102 13692 161066 179235 80552 40168 28048 108256 164724 64135 73457 47862 126186 179640 37087 ...
output:
-1
result:
ok 1 number(s): "-1"