| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 854502 |
2023-09-27T18:58:16 Z |
IBory |
Conspiracy (POI11_kon) |
C++17 |
|
1288 ms |
131072 KB |
#include <bits/stdc++.h>
using namespace std;
const int MAX = 5005;
bool G[MAX][MAX];
int N, V[MAX], out[MAX], cnt;
void Fail() {
cout << 0;
exit(0);
}
void DFS(int cur) {
cnt++;
for (int next = 1; next <= N; ++next) {
if (V[next] || !G[cur][next]) continue;
V[next] = 1;
DFS(next);
}
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int ans = 1, E = 0;
cin >> N;
for (int i = 1; i <= N; ++i) {
cin >> out[i];
E += out[i];
for (int j = 0; j < out[i]; ++j) {
int n;
cin >> n;
G[i][n] = 1;
}
}
int one = 0, comp = 0;
vector<int> isolated;
for (int i = 1; i <= N; ++i) {
if (V[i]) continue;
cnt = 0; V[i] = 1; DFS(i);
if (cnt == 1) {
one++;
isolated.push_back(i);
}
else comp++;
}
if (comp > 1) Fail();
int curNode = N - one;
do {
if (E == curNode * (curNode - 1)) break;
int cand = 0, ec = 1e9;
for (int i = 1; i <= N; ++i) {
if (out[i] > 0 && ec > out[i]) {
ec = out[i];
cand = i;
}
}
for (int i = 1; i <= N; ++i) {
if (!G[cand][i]) continue;
if (!G[i][cand]) Fail();
out[i]--;
G[cand][i] = 0;
}
out[cand] = 0;
isolated.push_back(cand);
E -= ec * 2;
} while (--curNode);
for (int i = 1; i <= N; ++i) {
if (!out[i]) continue;
int ok = 1;
for (int n : isolated) {
if (G[i][n]) {
ok = 0;
break;
}
}
if (ok) ans++;
}
cout << ans;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2580 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
8796 KB |
Output is correct |
| 2 |
Correct |
36 ms |
8788 KB |
Output is correct |
| 3 |
Correct |
159 ms |
23788 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
8796 KB |
Output is correct |
| 2 |
Correct |
59 ms |
10856 KB |
Output is correct |
| 3 |
Correct |
215 ms |
30796 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
13144 KB |
Output is correct |
| 2 |
Correct |
115 ms |
14932 KB |
Output is correct |
| 3 |
Correct |
352 ms |
44176 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
63 ms |
21076 KB |
Output is correct |
| 2 |
Correct |
259 ms |
21088 KB |
Output is correct |
| 3 |
Correct |
804 ms |
90484 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
525 ms |
24968 KB |
Output is correct |
| 2 |
Correct |
388 ms |
24908 KB |
Output is correct |
| 3 |
Correct |
1161 ms |
26068 KB |
Output is correct |
| 4 |
Incorrect |
1288 ms |
131072 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
