oj.uz

Submission #949720

# Submission time Handle Problem Language Result Execution time Memory
949720 2024-03-19T15:25:40 Z NourWael Bosses (BOI16_bosses) C++17
0 / 100
 1 ms 604 KB 
#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;
   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);
      }
   }
   
   int g = dfs(st,0);
   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

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

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Incorrect 1 ms 604 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Incorrect 1 ms 604 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Incorrect 1 ms 604 KB Output isn't correct
4 Halted 0 ms 0 KB -