# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
68896 |
2018-08-19T07:57:59 Z |
Abelyan |
Bosses (BOI16_bosses) |
C++17 |
|
817 ms |
1560 KB |
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cassert>
#include <climits>
#include <cstdio>
using namespace std;
typedef long long ll;
struct item {
int v, dpth;
};
const int N = 5006;
vector<int> g[N];
int col[N];
ll ans;
int n;
queue<item> q;
void bfs(int v,int cl) {
int k=1;
q.push({ v,1 });
col[v] = cl;
while (!q.empty()) {
item tv = q.front();
q.pop();
ans += (ll)tv.dpth;
for (auto to : g[tv.v]) {
if (col[to] == cl) continue;
//cout << to << endl;
col[to] = cl;
//cout << to << endl;
k++;
q.push({ to,tv.dpth + 1 });
}
}
if (k != n)ans = LLONG_MAX;
}
int main() {
//freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cin >> n;
for (int i = 0; i < n; i++) {
int k;
cin >> k;
for (int j = 0; j < k; j++) {
int a;
cin >> a;
g[a].push_back(i+1);
}
}
ll mn=LLONG_MAX;
for (int i = 1; i <= n; i++) {
ans = 0;
bfs(i, i);
//cout << i << " " << ans << endl;
mn = min(mn, ans);
}
if (mn == LLONG_MAX)assert(0);
cout << mn << endl;
system("pause");
return 0;
}
Compilation message
bosses.cpp: In function 'int main()':
bosses.cpp:66:8: warning: ignoring return value of 'int system(const char*)', declared with attribute warn_unused_result [-Wunused-result]
system("pause");
~~~~~~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
504 KB |
Output is correct |
2 |
Correct |
3 ms |
520 KB |
Output is correct |
3 |
Correct |
2 ms |
676 KB |
Output is correct |
4 |
Correct |
2 ms |
824 KB |
Output is correct |
5 |
Correct |
2 ms |
824 KB |
Output is correct |
6 |
Correct |
3 ms |
868 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
504 KB |
Output is correct |
2 |
Correct |
3 ms |
520 KB |
Output is correct |
3 |
Correct |
2 ms |
676 KB |
Output is correct |
4 |
Correct |
2 ms |
824 KB |
Output is correct |
5 |
Correct |
2 ms |
824 KB |
Output is correct |
6 |
Correct |
3 ms |
868 KB |
Output is correct |
7 |
Correct |
2 ms |
872 KB |
Output is correct |
8 |
Correct |
3 ms |
876 KB |
Output is correct |
9 |
Correct |
2 ms |
968 KB |
Output is correct |
10 |
Correct |
2 ms |
1004 KB |
Output is correct |
11 |
Correct |
3 ms |
1004 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
504 KB |
Output is correct |
2 |
Correct |
3 ms |
520 KB |
Output is correct |
3 |
Correct |
2 ms |
676 KB |
Output is correct |
4 |
Correct |
2 ms |
824 KB |
Output is correct |
5 |
Correct |
2 ms |
824 KB |
Output is correct |
6 |
Correct |
3 ms |
868 KB |
Output is correct |
7 |
Correct |
2 ms |
872 KB |
Output is correct |
8 |
Correct |
3 ms |
876 KB |
Output is correct |
9 |
Correct |
2 ms |
968 KB |
Output is correct |
10 |
Correct |
2 ms |
1004 KB |
Output is correct |
11 |
Correct |
3 ms |
1004 KB |
Output is correct |
12 |
Correct |
7 ms |
1156 KB |
Output is correct |
13 |
Correct |
7 ms |
1188 KB |
Output is correct |
14 |
Correct |
210 ms |
1240 KB |
Output is correct |
15 |
Correct |
5 ms |
1300 KB |
Output is correct |
16 |
Correct |
798 ms |
1428 KB |
Output is correct |
17 |
Correct |
817 ms |
1496 KB |
Output is correct |
18 |
Correct |
816 ms |
1560 KB |
Output is correct |