# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
79519 |
2018-10-15T01:27:38 Z |
Vinhspm |
Bosses (BOI16_bosses) |
C++14 |
|
718 ms |
996 KB |
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
typedef pair<int, int> ii;
const int N = 5005;
const int oo = 1e9;
int n, ans = oo;
bool visit[N];
vector<int> vi[N];
void solve(int root) {
int sum = 0;
memset(visit, false, sizeof visit);
queue<ii> pq; pq.push(ii(root, 1));
visit[root] = true;
while(!pq.empty()) {
ii cur = pq.front();
pq.pop();
sum += cur.se;
for(int v: vi[cur.fi]) if(!visit[v]){
visit[v] = true;
pq.push(ii(v, cur.se + 1));
}
}
for(int i = 1; i <= n; ++i) if(!visit[i]) return;
ans = min(ans, sum);
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 1; i <= n; ++i) {
int x; cin >> x;
for(int j = 1; j <= x; ++j) {
int u; cin >> u;
vi[u].pb(i);
}
}
for(int i = 1; i <= n; ++i) solve(i);
cout << ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
504 KB |
Output is correct |
2 |
Correct |
2 ms |
636 KB |
Output is correct |
3 |
Correct |
2 ms |
636 KB |
Output is correct |
4 |
Correct |
2 ms |
636 KB |
Output is correct |
5 |
Correct |
2 ms |
636 KB |
Output is correct |
6 |
Correct |
2 ms |
636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
504 KB |
Output is correct |
2 |
Correct |
2 ms |
636 KB |
Output is correct |
3 |
Correct |
2 ms |
636 KB |
Output is correct |
4 |
Correct |
2 ms |
636 KB |
Output is correct |
5 |
Correct |
2 ms |
636 KB |
Output is correct |
6 |
Correct |
2 ms |
636 KB |
Output is correct |
7 |
Correct |
2 ms |
692 KB |
Output is correct |
8 |
Correct |
3 ms |
692 KB |
Output is correct |
9 |
Correct |
2 ms |
708 KB |
Output is correct |
10 |
Correct |
3 ms |
720 KB |
Output is correct |
11 |
Correct |
3 ms |
736 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
504 KB |
Output is correct |
2 |
Correct |
2 ms |
636 KB |
Output is correct |
3 |
Correct |
2 ms |
636 KB |
Output is correct |
4 |
Correct |
2 ms |
636 KB |
Output is correct |
5 |
Correct |
2 ms |
636 KB |
Output is correct |
6 |
Correct |
2 ms |
636 KB |
Output is correct |
7 |
Correct |
2 ms |
692 KB |
Output is correct |
8 |
Correct |
3 ms |
692 KB |
Output is correct |
9 |
Correct |
2 ms |
708 KB |
Output is correct |
10 |
Correct |
3 ms |
720 KB |
Output is correct |
11 |
Correct |
3 ms |
736 KB |
Output is correct |
12 |
Correct |
7 ms |
736 KB |
Output is correct |
13 |
Correct |
5 ms |
736 KB |
Output is correct |
14 |
Correct |
176 ms |
816 KB |
Output is correct |
15 |
Correct |
5 ms |
816 KB |
Output is correct |
16 |
Correct |
653 ms |
996 KB |
Output is correct |
17 |
Correct |
714 ms |
996 KB |
Output is correct |
18 |
Correct |
718 ms |
996 KB |
Output is correct |