# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
478474 |
2021-10-07T16:58:16 Z |
Shin |
Bosses (BOI16_bosses) |
C++14 |
|
701 ms |
5280 KB |
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define all(x) x.begin(), x.end()
using namespace std;
const int N = 2e5 + 7;
const int MOD = 1e9 + 7; // 998244353;
const int INF = 1e9 + 7;
const long long INFLL = 1e18 + 7;
template <class X, class Y> bool minimize(X &a, Y b) {
if (a > b) return a = b, true;
return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
if (a < b) return a = b, true;
return false;
}
int n;
vector<int> adj[N];
void solve(void) {
cin >> n;
for (int i = 1; i <= n; i ++) {
int k; cin >> k;
while (k --) {
int v; cin >> v;
adj[v].push_back(i);
}
}
long long res = INFLL;
for (int root = 1; root <= n; root ++) {
queue<int> q;
q.push(root);
vector<int> level(n + 1, 0);
level[root] = 1;
long long sum = 0;
int cnt = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
sum += level[u];
cnt ++;
for (int v: adj[u]) if (level[v] == 0) {
level[v] = level[u] + 1;
q.push(v);
}
}
if (cnt == n) minimize(res, sum);
}
cout << res;
}
int main(void) {
cin.tie(0)->sync_with_stdio(0);
int test = 1;
// cin >> test;
while (test --) {
solve();
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
4940 KB |
Output is correct |
3 |
Correct |
3 ms |
4940 KB |
Output is correct |
4 |
Correct |
4 ms |
4944 KB |
Output is correct |
5 |
Correct |
3 ms |
4944 KB |
Output is correct |
6 |
Correct |
3 ms |
5016 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
4940 KB |
Output is correct |
3 |
Correct |
3 ms |
4940 KB |
Output is correct |
4 |
Correct |
4 ms |
4944 KB |
Output is correct |
5 |
Correct |
3 ms |
4944 KB |
Output is correct |
6 |
Correct |
3 ms |
5016 KB |
Output is correct |
7 |
Correct |
4 ms |
4944 KB |
Output is correct |
8 |
Correct |
4 ms |
5012 KB |
Output is correct |
9 |
Correct |
3 ms |
4944 KB |
Output is correct |
10 |
Correct |
3 ms |
4944 KB |
Output is correct |
11 |
Correct |
3 ms |
4944 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
4940 KB |
Output is correct |
3 |
Correct |
3 ms |
4940 KB |
Output is correct |
4 |
Correct |
4 ms |
4944 KB |
Output is correct |
5 |
Correct |
3 ms |
4944 KB |
Output is correct |
6 |
Correct |
3 ms |
5016 KB |
Output is correct |
7 |
Correct |
4 ms |
4944 KB |
Output is correct |
8 |
Correct |
4 ms |
5012 KB |
Output is correct |
9 |
Correct |
3 ms |
4944 KB |
Output is correct |
10 |
Correct |
3 ms |
4944 KB |
Output is correct |
11 |
Correct |
3 ms |
4944 KB |
Output is correct |
12 |
Correct |
7 ms |
5072 KB |
Output is correct |
13 |
Correct |
6 ms |
5072 KB |
Output is correct |
14 |
Correct |
125 ms |
5132 KB |
Output is correct |
15 |
Correct |
12 ms |
5072 KB |
Output is correct |
16 |
Correct |
562 ms |
5212 KB |
Output is correct |
17 |
Correct |
701 ms |
5232 KB |
Output is correct |
18 |
Correct |
701 ms |
5280 KB |
Output is correct |