# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
713630 |
2023-03-22T17:04:10 Z |
_martynas |
Bosses (BOI16_bosses) |
C++11 |
|
653 ms |
652 KB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
const int MOD = 1e9+7;
#define F first
#define S second
#define PB push_back
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
void FASTIO() {ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); }
const int MXN = 5005;
int n;
vi adj[MXN];
ll bfs(int s) {
ll cost = 1;
vector<bool> visited(n+1);
queue<pii> Q;
visited[s] = true;
Q.push({s, 1});
while(!Q.empty()) {
int u = Q.front().F, d = Q.front().S;
Q.pop();
for(int v : adj[u]) if(!visited[v]) {
visited[v] = true;
Q.push({v, d+1});
cost += d+1;
}
}
if(count(all(visited), true) != n) return 1LL*n*n;
return cost;
}
int main() {
FASTIO();
cin >> n;
for(int i = 1; i <= n; i++) {
int m; cin >> m;
for(int j = 0; j < m; j++) {
int p; cin >> p;
adj[p].PB(i);
}
}
ll ans = 1LL*n*n;
for(int i = 1; i <= n; i++) {
ll cost = bfs(i);
ans = min(ans, cost);
}
cout << ans << "\n";
return 0;
}
/*
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
356 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
356 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
436 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
356 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
436 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
4 ms |
468 KB |
Output is correct |
13 |
Correct |
3 ms |
468 KB |
Output is correct |
14 |
Correct |
152 ms |
536 KB |
Output is correct |
15 |
Correct |
22 ms |
468 KB |
Output is correct |
16 |
Correct |
494 ms |
636 KB |
Output is correct |
17 |
Correct |
651 ms |
652 KB |
Output is correct |
18 |
Correct |
653 ms |
644 KB |
Output is correct |