# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
973819 |
2024-05-02T11:25:50 Z |
Halym2007 |
Bosses (BOI16_bosses) |
C++17 |
|
6 ms |
1116 KB |
#include <bits/stdc++.h>
using namespace std;
const int N = 2e2 + 5;
#define ll long long
#define pb push_back
#define sz size()
map <int, int> mp[N];
int n, val[N][N], sub[N], vis[N];
vector <int> v[N], p[N];
void solve (int x, int pr) {
for (int i : p[x]) {
if (i == pr) continue;
solve (i, x);
sub[x] += sub[i];
}
sub[x]++;
}
int root (int x) {
queue <int> q;
for (int i = 1; i <= n; ++i) {
vis[i] = 0;
sub[i] = 0;
p[i].clear();
}
q.push(x);
vis[x] = 1;
while (!q.empty()) {
int x = q.front();
q.pop();
for (int i : v[x]) {
if (vis[i]) continue;
p[x].pb (i);
vis[i] = 1;
q.push(i);
}
}
for (int i = 1; i <= n; ++i) {
if (!vis[i]) return -1;
}
solve (x, -1);
int ret = 0;
for (int i = 1; i <= n; ++i) {
ret += sub[i];
}
return ret;
}
int main () {
// freopen ("input.txt", "r", stdin);
cin >> n;
for (int i = 1; i <= n; ++i) {
int k;
cin >> k;
for (int j = 1; j <= k; ++j) {
cin >> val[i][j];
mp[i][val[i][j]] = 1;
v[val[i][j]].pb (i);
}
}
int jog = 1e9;
for (int i = 1; i <= n; ++i) {
int jj = root (i);
if (~jj) {
jog = min (jog, jj);
}
}
cout << jog;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
6 ms |
1116 KB |
Output is correct |
13 |
Correct |
5 ms |
1116 KB |
Output is correct |
14 |
Runtime error |
1 ms |
860 KB |
Execution killed with signal 11 |
15 |
Halted |
0 ms |
0 KB |
- |