This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
///©Waschbar
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5000;
const int INF = 1e9;
const long long MOD = 1e9+7;
int n, ans;
vector < vector < int > > g(MAXN+1);
int solve(int f) {
vector <int> siz(n+1,0);
vector <bool> used(n+1,0);
queue <int> Q;
stack < pair<int,int> > st;
Q.push(f);
st.push({f,0});
used[f] = 1;
while(!Q.empty()){
f = Q.front();
Q.pop();
for(int i = 0; i < g[f].size(); i++){
int to = g[f][i];
if(used[to]) continue;
Q.push(to);
st.push({to,f});
used[to] = 1;
}
}
if(st.size() != n) return INF;
int cnt = 0;
while(!st.empty()) {
f = st.top().first;
int p = st.top().second;
st.pop();
siz[f]++; cnt += siz[f];
siz[p] += siz[f];
}
return cnt;
}
int main() {
ios_base::sync_with_stdio(false);
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
cin >> n;
for(int f = 1,m; f <= n; f++) {
cin >> m;
for(int i = 1,x; i <= m; i++) {
cin >> x;
g[x].push_back(f);
}
}
ans = INF;
for(int i = 1; i <= n; i++)
ans = min(ans,solve(i));
cout << ans;
return 0;
}
Compilation message (stderr)
bosses.cpp: In function 'int solve(int)':
bosses.cpp:26:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < g[f].size(); i++){
~~^~~~~~~~~~~~~
bosses.cpp:35:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(st.size() != n) return INF;
~~~~~~~~~~^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |