QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#638394#8760. 不等式ricofx#AC ✓64ms26164kbC++201.7kb2024-10-13 15:49:202024-10-13 15:49:22

Judging History

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

  • [2024-10-13 15:49:22]
  • 评测
  • 测评结果:AC
  • 用时:64ms
  • 内存:26164kb
  • [2024-10-13 15:49:20]
  • 提交

answer

//#pragma GCC optimize ("Ofast")
//#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
//mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const int mod = 998244353;
const int N = 2e5 + 5;

int n, m;
vector<int> G[N];
int in[N], vis[N];
ll dp[N];
vector<pii> ed[N];
void MAIN() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b, c;
        cin >> c >> b >> a;
        G[a].push_back(c);
        G[b].push_back(c);
        in[c]++;
        in[c]++;
        ed[c].push_back({a, b});
    }
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (!in[i]) q.push(i);
    }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        vis[u] = 1;
        dp[u] = 1;
        for (auto [a, b] : ed[u]) dp[u] = max(dp[u], dp[a] + dp[b]);
        for (int v : G[u]) {
            --in[v];
            if (!in[v]) q.push(v);
        }
    }
    ll sum = 0;
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) return cout << "-1\n", void();
        sum += dp[i];
    }
    if (sum > 1000000000ll) cout << -1 << '\n';
    else cout << sum << '\n';
}

int main() {
#ifdef LOCAL
    auto start = chrono::steady_clock::now();
    freopen("miku.in", "r", stdin);
    freopen("miku.out", "w", stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
    // cin >> T;
    while (T--) MAIN();
#ifdef LOCAL
    auto end = chrono::steady_clock::now();
    cout << "\nqwq: " <<  chrono::duration_cast<chrono::milliseconds>(end - start).count() << "ms\n";
#endif
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 7732kb

input:

3 1
1 2 2

output:

4

result:

ok 1 number(s): "4"

Test #2:

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

input:

3 1
1 2 3

output:

4

result:

ok 1 number(s): "4"

Test #3:

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

input:

3 1
1 2 2

output:

4

result:

ok 1 number(s): "4"

Test #4:

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

input:

3 1
1 2 2

output:

4

result:

ok 1 number(s): "4"

Test #5:

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

input:

3 1
1 2 2

output:

4

result:

ok 1 number(s): "4"

Test #6:

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

input:

5 1
1 2 2

output:

6

result:

ok 1 number(s): "6"

Test #7:

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

input:

5 1
1 2 2

output:

6

result:

ok 1 number(s): "6"

Test #8:

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

input:

5 1
1 2 2

output:

6

result:

ok 1 number(s): "6"

Test #9:

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

input:

5 1
1 2 3

output:

6

result:

ok 1 number(s): "6"

Test #10:

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

input:

5 2
1 2 3
2 3 4

output:

8

result:

ok 1 number(s): "8"

Test #11:

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

input:

10 1
1 2 3

output:

11

result:

ok 1 number(s): "11"

Test #12:

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

input:

10 1
1 2 2

output:

11

result:

ok 1 number(s): "11"

Test #13:

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

input:

10 2
1 2 3
2 3 4

output:

13

result:

ok 1 number(s): "13"

Test #14:

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

input:

10 2
1 2 2
2 3 4

output:

14

result:

ok 1 number(s): "14"

Test #15:

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

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: 5908kb

input:

20 1
1 2 2

output:

21

result:

ok 1 number(s): "21"

Test #17:

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

input:

20 2
1 2 3
2 3 3

output:

23

result:

ok 1 number(s): "23"

Test #18:

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

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: 1ms
memory: 7740kb

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: 5620kb

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: 7672kb

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: 5628kb

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: 0ms
memory: 7676kb

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: 7720kb

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: 7684kb

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: 0ms
memory: 7832kb

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: 0ms
memory: 5772kb

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: 5780kb

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: 1ms
memory: 7864kb

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: 0ms
memory: 5808kb

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: 2ms
memory: 8716kb

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: 2ms
memory: 8856kb

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: 3ms
memory: 8960kb

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: 6920kb

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: 0ms
memory: 9300kb

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: 4ms
memory: 17860kb

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: 7ms
memory: 18336kb

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: 12ms
memory: 18844kb

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: 12ms
memory: 19356kb

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: 64ms
memory: 26164kb

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"