QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #678188 | #8760. 不等式 | CORRECT# | WA | 0ms | 3920kb | C++20 | 1.5kb | 2024-10-26 14:14:59 | 2024-10-26 14:15:05 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
void work() {
int n, m;
cin >> n >> m;
vector<LL> ans(n+10, -1);
vector<vector<int> > to(n+10, vector<int>()), fto(n+10, vector<int>());
vector<int> du(n+10, 0);
vector<array<int, 2> > bian(m+10);
for (int i=1; i<=m; i++) {
int x, y, z; cin >> x >> y >> z;
du[x] += 2;
bian[i] = {y, z};
to[y].push_back(x);
to[z].push_back(x);
fto[x].push_back(i);
}
queue<int> qu;
for (int i=1; i<=n; i++) {
if (du[i] == 0) {
qu.push(i);
}
}
while (!qu.empty() ) {
int t = qu.front(); qu.pop();
LL num = 1;
for (auto &id : fto[t]) {
num = max(num, ans[bian[id][0]] + ans[bian[id][1]]);
}
ans[t] = num;
for (auto &id : to[t]) {
du[id] --;
if (du[id] == 0) {
qu.push(id);
}
}
}
bool bo = true;
LL sum = 0;
for (int i=1; i<=n; i++) {
if (ans[i] == -1) {
cout << -1 << '\n';
return;
}
sum += ans[i];
}
cout << sum << '\n';
}
int main()
{
#ifdef QHK
freopen("qi.in","r",stdin);
freopen("qi.out","w",stdout);
#endif
ios::sync_with_stdio(false); cin.tie(0);
int T=1;
// cin >> T;
while(T--){
work();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3540kb
input:
3 1 1 2 2
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
3 1 1 2 3
output:
4
result:
ok 1 number(s): "4"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
3 1 1 2 2
output:
4
result:
ok 1 number(s): "4"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3796kb
input:
3 1 1 2 2
output:
4
result:
ok 1 number(s): "4"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3476kb
input:
3 1 1 2 2
output:
4
result:
ok 1 number(s): "4"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3536kb
input:
5 1 1 2 2
output:
6
result:
ok 1 number(s): "6"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3520kb
input:
5 1 1 2 2
output:
6
result:
ok 1 number(s): "6"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
5 1 1 2 2
output:
6
result:
ok 1 number(s): "6"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3520kb
input:
5 1 1 2 3
output:
6
result:
ok 1 number(s): "6"
Test #10:
score: 0
Accepted
time: 0ms
memory: 3516kb
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: 3592kb
input:
10 1 1 2 3
output:
11
result:
ok 1 number(s): "11"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
10 1 1 2 2
output:
11
result:
ok 1 number(s): "11"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3728kb
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: 3532kb
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: 3584kb
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: 3592kb
input:
20 1 1 2 2
output:
21
result:
ok 1 number(s): "21"
Test #17:
score: 0
Accepted
time: 0ms
memory: 3596kb
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: 3588kb
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: 3588kb
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: 3800kb
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: 3604kb
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: 3812kb
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: 3744kb
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: 3612kb
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: 3612kb
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: 3708kb
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: 3868kb
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: 3920kb
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:
3241883559
result:
wrong answer 1st numbers differ - expected: '-1', found: '3241883559'