Submission #46776

#TimeUsernameProblemLanguageResultExecution timeMemory
46776WaschbarBosses (BOI16_bosses)C++17
100 / 100
1319 ms1528 KiB
///©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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...