Submission #292268

#TimeUsernameProblemLanguageResultExecution timeMemory
292268Ahmad_HasanBosses (BOI16_bosses)C++17
0 / 100
1 ms384 KiB
#include <bits/stdc++.h> using namespace std; vector<vector<int> >adj; vector<vector<int> >adj2; vector<int>vis; vector<int>vis2; pair<int,int> dfs(int cr){ vis[cr]=1; pair<int,int>tmp; tmp.first=0,tmp.second=0; int cntc=0,cnttl=0; for(int i=0;i<adj2[cr].size();i++){ if(!vis[adj2[cr][i]]){ tmp=dfs(adj2[cr][i]); cntc+=tmp.first; cnttl+=tmp.second; } } return {cntc+1,cnttl+cntc+1}; } void bfs(int cr){ queue<int>q; q.push(cr); vis2[cr]=1; while(!q.empty()){ int ncr=q.front(); q.pop(); for(int i=0;i<adj[ncr].size();i++){ if(!vis2[adj[ncr][i]]){ vis2[adj[ncr][i]]=1; adj2[ncr].push_back(adj[ncr][i]); q.push(adj[ncr][i]); } } } } int main() {///{} ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin>>n; adj=vector<vector<int> >(n+1); for(int i=1;i<=n;i++){ int nt; cin>>nt; while(nt--){ int tm; cin>>tm; adj[tm].push_back(i); } } int ans=INT_MAX; for(int i=1;i<=n;i++){ vis=vector<int> (n+1); vis2=vector<int> (n+1); adj2=vector<vector<int> > (n+1); bfs(i); int f=1; if(f) ans=min(ans,dfs(i).second); } cout<<ans<<'\n'; return 0; } /*** 4 1 2 1 1 1 2 1 2 */

Compilation message (stderr)

bosses.cpp: In function 'std::pair<int, int> dfs(int)':
bosses.cpp:13:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for(int i=0;i<adj2[cr].size();i++){
      |                 ~^~~~~~~~~~~~~~~~
bosses.cpp: In function 'void bfs(int)':
bosses.cpp:29:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         for(int i=0;i<adj[ncr].size();i++){
      |                     ~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...