# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
484212 |
2021-11-02T13:50:52 Z |
Sohsoh84 |
Bosses (BOI16_bosses) |
C++17 |
|
1111 ms |
27972 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define all(x) (x).begin(),(x).end()
#define X first
#define Y second
#define sep ' '
#define endl '\n'
#define debug(x) cerr << #x << ": " << x << endl;
const ll MAXN = 1e6 + 10;
int n, dist[MAXN];
vector<int> adj[MAXN];
inline ll calc(int v) {
memset(dist, 63, sizeof dist);
queue<int> q;
q.push(v);
dist[v] = 1;
ll ans = 0;
while (!q.empty()) {
v = q.front();
q.pop();
ans += dist[v];
for (int u : adj[v]) {
if (dist[v] + 1 < dist[u]) {
dist[u] = dist[v] + 1;
q.push(u);
}
}
}
for (int i = 1; i <= n; i++)
if (dist[i] > MAXN)
return MAXN * MAXN;
return ans;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) {
int k;
cin >> k;
for (int j = 0; j < k; j++) {
int x;
cin >> x;
adj[x].push_back(i);
}
}
ll ans = MAXN * MAXN;
for (int i = 1; i <= n; i++)
ans = min(ans, calc(i));
cout << ans << endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
27596 KB |
Output is correct |
2 |
Correct |
13 ms |
27596 KB |
Output is correct |
3 |
Correct |
13 ms |
27684 KB |
Output is correct |
4 |
Correct |
13 ms |
27644 KB |
Output is correct |
5 |
Correct |
13 ms |
27596 KB |
Output is correct |
6 |
Correct |
13 ms |
27596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
27596 KB |
Output is correct |
2 |
Correct |
13 ms |
27596 KB |
Output is correct |
3 |
Correct |
13 ms |
27684 KB |
Output is correct |
4 |
Correct |
13 ms |
27644 KB |
Output is correct |
5 |
Correct |
13 ms |
27596 KB |
Output is correct |
6 |
Correct |
13 ms |
27596 KB |
Output is correct |
7 |
Correct |
21 ms |
27712 KB |
Output is correct |
8 |
Correct |
17 ms |
27716 KB |
Output is correct |
9 |
Correct |
15 ms |
27596 KB |
Output is correct |
10 |
Correct |
21 ms |
27716 KB |
Output is correct |
11 |
Correct |
21 ms |
27668 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
27596 KB |
Output is correct |
2 |
Correct |
13 ms |
27596 KB |
Output is correct |
3 |
Correct |
13 ms |
27684 KB |
Output is correct |
4 |
Correct |
13 ms |
27644 KB |
Output is correct |
5 |
Correct |
13 ms |
27596 KB |
Output is correct |
6 |
Correct |
13 ms |
27596 KB |
Output is correct |
7 |
Correct |
21 ms |
27712 KB |
Output is correct |
8 |
Correct |
17 ms |
27716 KB |
Output is correct |
9 |
Correct |
15 ms |
27596 KB |
Output is correct |
10 |
Correct |
21 ms |
27716 KB |
Output is correct |
11 |
Correct |
21 ms |
27668 KB |
Output is correct |
12 |
Correct |
40 ms |
27784 KB |
Output is correct |
13 |
Correct |
35 ms |
27724 KB |
Output is correct |
14 |
Correct |
568 ms |
27784 KB |
Output is correct |
15 |
Correct |
462 ms |
27816 KB |
Output is correct |
16 |
Correct |
963 ms |
27888 KB |
Output is correct |
17 |
Correct |
1111 ms |
27916 KB |
Output is correct |
18 |
Correct |
1108 ms |
27972 KB |
Output is correct |