| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 865939 |
2023-10-25T04:56:31 Z |
maks007 |
Bosses (BOI16_bosses) |
C++14 |
|
1202 ms |
1664 KB |
#include "bits/stdc++.h"
using namespace std;
#define int long long
signed main () {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n, ans = LLONG_MAX;
cin >> n;
vector <int> g[n], g2[n];
for(int i = 0; i < n; i ++) {
int sz;
cin >> sz;
while(sz --) {
int v;
cin >> v;
g[v-1].push_back(i);
}
}
queue <int> q;
for(int i = 0; i < n; i ++) {
vector <int> dist(n, LLONG_MAX);
dist[i] = 0;
q.push(i);
vector <pair <int,int>> temp;
while(!q.empty()) {
int v = q.front();
q.pop();
for(auto u : g[v]) {
if(dist[u] == LLONG_MAX) {
temp.push_back({v, u});
dist[u] = dist[v] + 1;
q.push(u);
}
}
}
if(count(dist.begin(), dist.end(), LLONG_MAX)) continue;
vector <int> dp(n, 1);
function <void(int,int)> dfs=[&](int v, int p) {
for(auto u : g2[v]) {
if(p == u) continue;
dfs(u, v);
dp[v] += dp[u];
}
};
for(auto j : temp) g2[j.first].push_back(j.second);
dfs(i,-1);
ans = min(ans, accumulate(dp.begin(), dp.end(), 0LL));
for(auto &j : g2) j.clear();
}
cout << ans;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
344 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
344 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
1 ms |
348 KB |
Output is correct |
| 11 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
344 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
1 ms |
348 KB |
Output is correct |
| 11 |
Correct |
1 ms |
348 KB |
Output is correct |
| 12 |
Correct |
4 ms |
600 KB |
Output is correct |
| 13 |
Correct |
3 ms |
604 KB |
Output is correct |
| 14 |
Correct |
137 ms |
1212 KB |
Output is correct |
| 15 |
Correct |
26 ms |
1032 KB |
Output is correct |
| 16 |
Correct |
600 ms |
1180 KB |
Output is correct |
| 17 |
Correct |
1194 ms |
1664 KB |
Output is correct |
| 18 |
Correct |
1202 ms |
1352 KB |
Output is correct |
