Submission #949773

#	Time	Username	Problem	Language	Result	Execution time	Memory
949773		NourWael	Bosses (BOI16_bosses)	C++17	100 / 100	841 ms	1096 KiB

bosses

#include <bits/stdc++.h>
#define int long long
using namespace std; 
int const mxN = 5e3+5;
vector<int> adj[mxN];
vector<int> fin[mxN];
bool vis[mxN];
int n, sz[mxN];
int full;

int dfs ( int i, int p ) {
   int ans = 1;
   vis[i] = 1;
   for(auto it:fin[i]) {
      if(it==p) continue;
      ans += dfs(it, i);
   }
   full += ans;
   return ans;
}

int solve ( int st ) {
   memset(vis,0,sizeof vis); 
   full = 0;
   for(int i=1; i<=n; i++) fin[i].clear();
   queue<int> q;
   q.push(st);
   vis[st] = 1;
   
   while(q.size()) {
      int i = q.front();
      q.pop();

      for(auto it:adj[i]) {
          if(vis[it]) continue; 
          vis[it] = 1;
          q.push(it);
          fin[i].push_back(it);
      }
   }
   
   memset(vis,0,sizeof vis);
   int g = dfs(st,0);
   for(int i=1; i<=n; i++) if(!vis[i]) return 3e18;
   return full;

}
signed main() {
 
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    
    cin>>n;
    for(int i=1; i<=n; i++) {
      int c; cin>>c;
      while(c--) {
         int x; cin>>x;
         adj[x].push_back(i);
      }
    }
    
    int ans = 3e18;
    for(int i=1; i<=n; i++) { ans = min(ans, solve(i)); 
     }   
    cout<<ans;
   return 0;
}

Compilation message (stderr)

bosses.cpp: In function 'long long int solve(long long int)':
bosses.cpp:43:8: warning: unused variable 'g' [-Wunused-variable]
   43 |    int g = dfs(st,0);
      |        ^

• Subtask 1: 22 / 22
• Subtask 2: 45 / 45
• Subtask 3: 33 / 33