This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
vector<vector<long long>> adg;
vector<vector<long long>> adgtree;
void dfs(long long cur, long long salary[]){
if(adgtree[cur].empty()){
salary[cur]= 1;
}
else{
long long cnt = 0;
for(auto next : adgtree[cur]){
dfs(next, salary);
cnt+=salary[next];
}
salary[cur]=cnt+1;
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
long long n;
cin >> n;
adg.resize(n);
for(long long i=0; i<n; i++){
long long a;
cin >> a;
for(long long j=0; j<a; j++){
long long b;
cin >> b;
adg[b-1].push_back(i);
}
}
long long ans = -1;
for(long long root = 0; root<n; root++){
bool vsted[n] = {false};
adgtree.clear();
adgtree.resize(n);
queue<int> que;
que.push(root);
vsted[root]=true;
while(!que.empty()){
long long cur = que.front();
que.pop();
for(auto u : adg[cur]){
if(!vsted[u]){
vsted[u]=true;
adgtree[cur].push_back(u);
que.push(u);
}
}
}
long long salary[n];
dfs(root, salary);
long long curans = 0;
for(long long i=0; i<n; i++){
curans+=salary[i];
}
if(ans==-1){
ans = curans;
}
else{
ans = min(ans, curans);
}
}
cout << ans << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |