QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#569552#8760. 不等式ranxiWA 0ms3876kbC++141.5kb2024-09-17 00:38:422024-09-17 00:38:42

Judging History

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

  • [2024-09-17 00:38:42]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3876kb
  • [2024-09-17 00:38:42]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define alls(x) x.begin(),x.end()
#define ull unsigned long long
#define lowbit(x) x&-x
#define lc p<<1
#define rc p<<1|1
#define PII pair<int,int>
#define vi vector<int>
using namespace std;
const int mod = 998244353;
const int N = 2e5+10;
int n,m;
void solve()
{
    cin >> n >> m;
    int x,y,z;
    vector<PII>E[n];
    vi d(n);
    for(int i = 0;i<m;i++){
        cin >> x >> y >> z;
        --x,--y,--z;
        E[x].push_back({y,z});
        d[y]++,d[z]++;
    }
    vector<int> q;
    for(int i = 0;i < n; i++){
        if(d[i] == 0){
            q.push_back(i);
        }
    }
    for(int i = 0;i < q.size(); i++){
        int x = q[i];
        for(auto [y,z] : E[x]){
            for(auto a : {y,z}){
                if(--d[a] == 0) q.push_back(a);
            }
        }
    }

    if(q.size() != n){
        cout << -1 <<endl;
        return;
    }

    vector<int> a(n,1);
    int ans = 0;
    for(int i = n - 1;i >= 0 ;i--){
        int x= q[i];
        for(auto [y,w] : E[x]){
            a[x] = max(a[x], a[y] + a[w]);
        }
    }
    for(int i = 0 ;i < n ;i++){
        ans += a[i];
    }
//    if(ans > 1e9){
//        cout << -1 << '\n';
//        return;
//    }
    cout << ans << '\n';
}
signed main()
{
    cout<<fixed<<setprecision(6);
    ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    int _ = 1;
//    cin >> _;
    while(_--)solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3576kb

input:

3 1
1 2 2

output:

4

result:

ok 1 number(s): "4"

Test #2:

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

input:

3 1
1 2 3

output:

4

result:

ok 1 number(s): "4"

Test #3:

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

input:

3 1
1 2 2

output:

4

result:

ok 1 number(s): "4"

Test #4:

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

input:

3 1
1 2 2

output:

4

result:

ok 1 number(s): "4"

Test #5:

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

input:

3 1
1 2 2

output:

4

result:

ok 1 number(s): "4"

Test #6:

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

input:

5 1
1 2 2

output:

6

result:

ok 1 number(s): "6"

Test #7:

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

input:

5 1
1 2 2

output:

6

result:

ok 1 number(s): "6"

Test #8:

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

input:

5 1
1 2 2

output:

6

result:

ok 1 number(s): "6"

Test #9:

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

input:

5 1
1 2 3

output:

6

result:

ok 1 number(s): "6"

Test #10:

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

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

input:

10 1
1 2 3

output:

11

result:

ok 1 number(s): "11"

Test #12:

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

input:

10 1
1 2 2

output:

11

result:

ok 1 number(s): "11"

Test #13:

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

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

input:

10 2
1 2 2
2 3 4

output:

14

result:

ok 1 number(s): "14"

Test #15:

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

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

input:

20 1
1 2 2

output:

21

result:

ok 1 number(s): "21"

Test #17:

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

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

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

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

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

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

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

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

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

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

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

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: -100
Wrong Answer
time: 0ms
memory: 3756kb

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:

-1053083737

result:

wrong answer 1st numbers differ - expected: '-1', found: '-1053083737'