QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#604617 | #8760. 不等式 | xing4c# | WA | 3ms | 10740kb | C++14 | 1.4kb | 2024-10-02 12:32:51 | 2024-10-02 12:32:51 |
Judging History
answer
#include <bits/stdc++.h>
#define NOSYNC ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define endl '\n'
using namespace std;
using ll = long long;
using ull = unsigned long long;
const int N = 200005;
// -------------- Templates Above -------------------------
int a[N]; int n, m;
vector<int> G[N];
int in[N]; int vis[N]; int d[N];
void dfs1(int x) {
// cout << "dfs1: " << x << endl;
if(vis[x]) return;
vis[x] = 1;
if(G[x].empty()) {
a[x] = 1;
return;
}
priority_queue<int> q;
for(int y : G[x]) {
dfs1(y);
q.push(a[y]);
}
int v1 = q.top(); q.pop();
int v2 = q.top(); q.pop();
a[x] = v1 + v2;
}
signed main() {
NOSYNC;
cin >> n >> m;
for(int i = 1; i <= m; i ++) {
int x, y, z;
cin >> x >> y >> z;
G[x].push_back(y);
G[x].push_back(z);
++ in[y]; ++ in[z];
++ d[y]; ++ d[z];
}
queue<int> q;
for(int i = 1; i <= n; i ++) {
if(!d[i]) {
q.push(i);
}
}
while(!q.empty()) {
int u = q.front(); q.pop();
vis[u] = 1;
for(int v : G[u]) {
-- d[v];
if(!d[v]) {
q.push(v);
}
}
}
for(int i = 1; i <= n; i ++) {
if(!vis[i]) {
cout << -1 << endl;
return 0;
}
}
for(int i = 1; i <= n; i ++) vis[i] = 0;
for(int i = 1; i <= n; i ++) {
if(!in[i] && !vis[i]) dfs1(i);
}
int ans = 0;
for(int i = 1; i <= n; i ++) {
ans += a[i];
}
cout << ans << endl;
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 9696kb
input:
3 1 1 2 2
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 2ms
memory: 9964kb
input:
3 1 1 2 3
output:
4
result:
ok 1 number(s): "4"
Test #3:
score: 0
Accepted
time: 3ms
memory: 10460kb
input:
3 1 1 2 2
output:
4
result:
ok 1 number(s): "4"
Test #4:
score: 0
Accepted
time: 3ms
memory: 9692kb
input:
3 1 1 2 2
output:
4
result:
ok 1 number(s): "4"
Test #5:
score: 0
Accepted
time: 0ms
memory: 10512kb
input:
3 1 1 2 2
output:
4
result:
ok 1 number(s): "4"
Test #6:
score: 0
Accepted
time: 2ms
memory: 9716kb
input:
5 1 1 2 2
output:
6
result:
ok 1 number(s): "6"
Test #7:
score: 0
Accepted
time: 0ms
memory: 10248kb
input:
5 1 1 2 2
output:
6
result:
ok 1 number(s): "6"
Test #8:
score: 0
Accepted
time: 2ms
memory: 9764kb
input:
5 1 1 2 2
output:
6
result:
ok 1 number(s): "6"
Test #9:
score: 0
Accepted
time: 2ms
memory: 9700kb
input:
5 1 1 2 3
output:
6
result:
ok 1 number(s): "6"
Test #10:
score: 0
Accepted
time: 0ms
memory: 9696kb
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: 9988kb
input:
10 1 1 2 3
output:
11
result:
ok 1 number(s): "11"
Test #12:
score: 0
Accepted
time: 0ms
memory: 10016kb
input:
10 1 1 2 2
output:
11
result:
ok 1 number(s): "11"
Test #13:
score: 0
Accepted
time: 0ms
memory: 9692kb
input:
10 2 1 2 3 2 3 4
output:
13
result:
ok 1 number(s): "13"
Test #14:
score: 0
Accepted
time: 2ms
memory: 9696kb
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: 9992kb
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: 2ms
memory: 10016kb
input:
20 1 1 2 2
output:
21
result:
ok 1 number(s): "21"
Test #17:
score: 0
Accepted
time: 0ms
memory: 10628kb
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: 10316kb
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: 2ms
memory: 10484kb
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: 2ms
memory: 10740kb
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: 9888kb
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: 10056kb
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: 2ms
memory: 8696kb
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: 9876kb
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: 9756kb
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: 9940kb
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: 8852kb
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: 3ms
memory: 10332kb
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:
-1053083736
result:
wrong answer 1st numbers differ - expected: '-1', found: '-1053083736'