# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
494342 |
2021-12-15T08:52:06 Z |
ahmeteren |
Bosses (BOI16_bosses) |
C++17 |
|
1338 ms |
960 KB |
#include<bits/stdc++.h>
using namespace std;
const int N = 5e3 + 5;
int cnt = 0, c[N], temp;
bool visited[N];
vector<int> adj[N], vec[N];
void bfs(int node)
{
queue<int> q;
q.push(node);
visited[node] = true;
cnt = 1;
while(!q.empty())
{
int node = q.front();
q.pop();
for(auto to : adj[node])
{
if(!visited[to])
{
cnt++;
visited[to] = true;
q.push(to);
vec[node].push_back(to);
}
}
}
}
void dfs(int node, int par)
{
for(auto to : vec[node])
{
if(to == par)
continue;
dfs(to, node);
c[node] += c[to];
}
c[node]++;
temp += c[node];
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// #ifndef ONLINE_JUDGE
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
// #endif
int n, cevap = 1e9;
cin >> n;
for(int i = 1; i <= n; i++)
{
int k;
cin >> k;
for(int j = 0; j < k; j++)
{
int b;
cin >> b;
adj[b].push_back(i);
}
}
for(int i = 1; i <= n; i++)
{
for(int i = 1; i <= n; i++)
vec[i].clear(), visited[i] = false, c[i] = 0;
cnt = 0;
bfs(i);
if(cnt == n)
{
temp = 0;
dfs(i, 0);
cevap = min(cevap, temp);
}
}
cout << cevap << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
1 ms |
460 KB |
Output is correct |
3 |
Correct |
1 ms |
460 KB |
Output is correct |
4 |
Correct |
1 ms |
460 KB |
Output is correct |
5 |
Correct |
1 ms |
460 KB |
Output is correct |
6 |
Correct |
1 ms |
460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
1 ms |
460 KB |
Output is correct |
3 |
Correct |
1 ms |
460 KB |
Output is correct |
4 |
Correct |
1 ms |
460 KB |
Output is correct |
5 |
Correct |
1 ms |
460 KB |
Output is correct |
6 |
Correct |
1 ms |
460 KB |
Output is correct |
7 |
Correct |
1 ms |
560 KB |
Output is correct |
8 |
Correct |
1 ms |
556 KB |
Output is correct |
9 |
Correct |
1 ms |
460 KB |
Output is correct |
10 |
Correct |
1 ms |
460 KB |
Output is correct |
11 |
Correct |
1 ms |
460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
1 ms |
460 KB |
Output is correct |
3 |
Correct |
1 ms |
460 KB |
Output is correct |
4 |
Correct |
1 ms |
460 KB |
Output is correct |
5 |
Correct |
1 ms |
460 KB |
Output is correct |
6 |
Correct |
1 ms |
460 KB |
Output is correct |
7 |
Correct |
1 ms |
560 KB |
Output is correct |
8 |
Correct |
1 ms |
556 KB |
Output is correct |
9 |
Correct |
1 ms |
460 KB |
Output is correct |
10 |
Correct |
1 ms |
460 KB |
Output is correct |
11 |
Correct |
1 ms |
460 KB |
Output is correct |
12 |
Correct |
5 ms |
716 KB |
Output is correct |
13 |
Correct |
4 ms |
716 KB |
Output is correct |
14 |
Correct |
183 ms |
876 KB |
Output is correct |
15 |
Correct |
31 ms |
716 KB |
Output is correct |
16 |
Correct |
646 ms |
908 KB |
Output is correct |
17 |
Correct |
1338 ms |
960 KB |
Output is correct |
18 |
Correct |
1299 ms |
940 KB |
Output is correct |