| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 113327 |
2019-05-25T05:19:11 Z |
MAMBA |
Bosses (BOI16_bosses) |
C++17 |
|
419 ms |
760 KB |
#include <bits/stdc++.h>
using namespace std;
#define rep(i , j , k) for (int i = j; i < (int)k; i++)
#define pb push_back
#define mt make_tuple
#define all(x) x.begin(),x.end()
typedef long long ll;
typedef pair<int , int> pii;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef complex<ld> point;
typedef pair<ld , ld> pld;
typedef vector<int> vi;
inline void fileIO(string s) {
// freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
template<class T , class S>
inline bool smin(T &a, S b) { return (T)b < a ? a = b , 1 : 0; }
template<class T , class S>
inline bool smax(T &a, S b) { return a < (T)b ? a = b , 1 : 0; }
constexpr int N = 5e3 + 10;
constexpr int MOD = 1e6 + 7;
template<typename T>
inline T mod(T &v) { return v = (v % MOD + MOD) % MOD; }
template<typename S, typename T>
inline S add(S &l, T r) { return mod(l += r); }
int n, m;
int dist[N];
vi adj[N];
int q[N], l , r;
int ans = 1e9;
inline void bfs(int s) {
memset(dist,63, sizeof(dist));
dist[s] = 1;
q[l = r = 0] = s;
r++;
while (l < r) {
int v = q[l++];
for (auto e :adj[v])
if (smin(dist[e] , dist[v] + 1))
q[r++] = e;
}
if (r == n)
smin(ans , accumulate(dist , dist + n , 0));
return;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#ifndef LOCAL
//fileIO("superposition");
#endif
cin >> n;
rep(i , 0 , n)
{
int k; cin >> k;
rep(j , 0 , k) {
int v; cin >> v;
adj[v - 1].pb(i);
}
}
rep(i , 0 , n)
bfs(i);
cout << ans << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
512 KB |
Output is correct |
| 2 |
Correct |
2 ms |
512 KB |
Output is correct |
| 3 |
Correct |
2 ms |
512 KB |
Output is correct |
| 4 |
Correct |
2 ms |
512 KB |
Output is correct |
| 5 |
Correct |
2 ms |
512 KB |
Output is correct |
| 6 |
Correct |
2 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
512 KB |
Output is correct |
| 2 |
Correct |
2 ms |
512 KB |
Output is correct |
| 3 |
Correct |
2 ms |
512 KB |
Output is correct |
| 4 |
Correct |
2 ms |
512 KB |
Output is correct |
| 5 |
Correct |
2 ms |
512 KB |
Output is correct |
| 6 |
Correct |
2 ms |
512 KB |
Output is correct |
| 7 |
Correct |
2 ms |
512 KB |
Output is correct |
| 8 |
Correct |
2 ms |
512 KB |
Output is correct |
| 9 |
Correct |
3 ms |
512 KB |
Output is correct |
| 10 |
Correct |
2 ms |
512 KB |
Output is correct |
| 11 |
Correct |
2 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
512 KB |
Output is correct |
| 2 |
Correct |
2 ms |
512 KB |
Output is correct |
| 3 |
Correct |
2 ms |
512 KB |
Output is correct |
| 4 |
Correct |
2 ms |
512 KB |
Output is correct |
| 5 |
Correct |
2 ms |
512 KB |
Output is correct |
| 6 |
Correct |
2 ms |
512 KB |
Output is correct |
| 7 |
Correct |
2 ms |
512 KB |
Output is correct |
| 8 |
Correct |
2 ms |
512 KB |
Output is correct |
| 9 |
Correct |
3 ms |
512 KB |
Output is correct |
| 10 |
Correct |
2 ms |
512 KB |
Output is correct |
| 11 |
Correct |
2 ms |
512 KB |
Output is correct |
| 12 |
Correct |
5 ms |
640 KB |
Output is correct |
| 13 |
Correct |
4 ms |
640 KB |
Output is correct |
| 14 |
Correct |
87 ms |
620 KB |
Output is correct |
| 15 |
Correct |
5 ms |
640 KB |
Output is correct |
| 16 |
Correct |
419 ms |
640 KB |
Output is correct |
| 17 |
Correct |
416 ms |
760 KB |
Output is correct |
| 18 |
Correct |
415 ms |
728 KB |
Output is correct |
