# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
260276 |
2020-08-10T02:08:45 Z |
Namnamseo |
Bosses (BOI16_bosses) |
C++17 |
|
1089 ms |
888 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
typedef pair<ll,ll> pll;
void cppio(){ ios_base::sync_with_stdio(0); cin.tie(0); }
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define eb emplace_back
#define x first
#define y second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define sz(x) (int)(x).size()
#define XY(p) p.x, p.y
int n;
vector<int> e[5010];
bitset<5001> vis;
ll s[5010];
ll d[5010];
int q[5010];
int par[5010];
const ll inf = 1ll<<60;
ll f(int r)
{
vis.reset(); vis[r] = 1;
int head = 1, tail = 0; q[0] = r; par[r] = -1;
while(head>tail) {
int x = q[tail++];
for (int y:e[x]) if (!vis[y]) vis[y]=1, par[y]=x, q[head++]=y;
}
if (head != n) return inf;
for (int i=n-1; 0<=i; --i) {
int x = q[i]; s[x] = 1; d[x] = 0;
for (int y:e[x]) if (par[y] == x) s[x] += s[y], d[x] += d[y];
d[x] += s[x];
}
return d[r];
}
int main()
{
cppio(); cin >> n;
rrep(i, n) {
int k; cin >> k;
for(;k--;) {
int j; cin >> j;
e[j].pb(i);
}
}
ll ans = inf;
rrep(i, n) ans = min(ans, f(i));
cout << ans << endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
512 KB |
Output is correct |
2 |
Correct |
1 ms |
512 KB |
Output is correct |
3 |
Correct |
1 ms |
512 KB |
Output is correct |
4 |
Correct |
1 ms |
512 KB |
Output is correct |
5 |
Correct |
1 ms |
512 KB |
Output is correct |
6 |
Correct |
1 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
512 KB |
Output is correct |
2 |
Correct |
1 ms |
512 KB |
Output is correct |
3 |
Correct |
1 ms |
512 KB |
Output is correct |
4 |
Correct |
1 ms |
512 KB |
Output is correct |
5 |
Correct |
1 ms |
512 KB |
Output is correct |
6 |
Correct |
1 ms |
512 KB |
Output is correct |
7 |
Correct |
1 ms |
512 KB |
Output is correct |
8 |
Correct |
1 ms |
512 KB |
Output is correct |
9 |
Correct |
1 ms |
512 KB |
Output is correct |
10 |
Correct |
1 ms |
512 KB |
Output is correct |
11 |
Correct |
1 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
512 KB |
Output is correct |
2 |
Correct |
1 ms |
512 KB |
Output is correct |
3 |
Correct |
1 ms |
512 KB |
Output is correct |
4 |
Correct |
1 ms |
512 KB |
Output is correct |
5 |
Correct |
1 ms |
512 KB |
Output is correct |
6 |
Correct |
1 ms |
512 KB |
Output is correct |
7 |
Correct |
1 ms |
512 KB |
Output is correct |
8 |
Correct |
1 ms |
512 KB |
Output is correct |
9 |
Correct |
1 ms |
512 KB |
Output is correct |
10 |
Correct |
1 ms |
512 KB |
Output is correct |
11 |
Correct |
1 ms |
512 KB |
Output is correct |
12 |
Correct |
10 ms |
640 KB |
Output is correct |
13 |
Correct |
7 ms |
640 KB |
Output is correct |
14 |
Correct |
89 ms |
640 KB |
Output is correct |
15 |
Correct |
3 ms |
768 KB |
Output is correct |
16 |
Correct |
505 ms |
740 KB |
Output is correct |
17 |
Correct |
1058 ms |
768 KB |
Output is correct |
18 |
Correct |
1089 ms |
888 KB |
Output is correct |