# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
531299 |
2022-02-28T11:16:13 Z |
bonk |
Bosses (BOI16_bosses) |
C++14 |
|
1 ms |
460 KB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 5002;
vector<int>v[N];
bool vis[N];
vector<int>adj[N];
ll ans[N];
ll solve(int x){
if(adj[x].empty()){
ans[x] = 1;
return 1;
}
ll &ret = ans[x];
ret = 1;
for(auto nxt: adj[x]){
ret += solve(nxt);
}
return ret;
}
int main(){
memset(ans, -1, sizeof(ans));
int n; cin >> n;
for(int i = 1; i <= n; i++){
int k; cin >> k;
for(int j = 1; j <= k; j++){
int x; cin >> x;
v[x].push_back(i);
}
}
vector<pair<int, int>>a;
for(int i = 1; i <= n; i++){
a.emplace_back(v[i].size(), i);
}
sort(a.begin(), a.end(), greater<pair<int, int>>());
int root = a[0].second;
//queue<int>q;
//q.push(root);
vis[root] = true;
// while(!q.empty()){
// int now = q.front(); q.pop();
// for(auto x: v[now]){
// if(!vis[x]){
// vis[x] = true;
// adj[now].push_back(x);
// q.push(x);
// }
// }
// }
while(true){
bool ok = true;
for(int i = 0; i < n; i++){
for(auto x: v[a[i].second]){
if(!vis[x]){
//cout << a[i].second << " is a parent of " << x << endl;
ok = false;
vis[x] = true;
adj[a[i].second].push_back(x);
}
}
}
if(ok) break;
}
solve(root);
ll total = 0;
for(int i = 1; i <= n; i++){
total += ans[i];
}
cout << total << endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
1 ms |
460 KB |
Output is correct |
3 |
Incorrect |
1 ms |
460 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
1 ms |
460 KB |
Output is correct |
3 |
Incorrect |
1 ms |
460 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
1 ms |
460 KB |
Output is correct |
3 |
Incorrect |
1 ms |
460 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |