oj.uz

Submission #949611

# Submission time Handle Problem Language Result Execution time Memory
949611 2024-03-19T12:32:20 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(), s = 0;
      q.pop();
      set<int> st;

      for(auto it:adj[i]) {
          if(vis[it]) continue; 
          st.insert(it);
          fin[i].push_back(it);
      }
      
      set<pair<int,int>> p;
      for(auto it:adj[i]) {
         if(vis[it]) continue;
         int cnt = 0;
         for(auto t:adj[it]) {
            if(vis[t] || st.find(t)!=st.end()) continue;
            cnt++;
         }
         vis[it] = 1;
         p.insert({cnt,it});
      }

      if(p.size()==0) continue;
      auto it = p.end(); 
      while(it!=p.begin()) {
         it--;
         q.push((*it).second);
      }
   }
   
   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);
      }
    }
    
    for(int i=1; i<=n; i++) sz[i] = adj[i].size();
    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:29:26: warning: unused variable 's' [-Wunused-variable]
   29 |       int i = q.front(), s = 0;
      |                          ^
bosses.cpp:59:8: warning: unused variable 'g' [-Wunused-variable]
   59 |    int g = dfs(st,0);
      |        ^

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 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 604 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 604 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 -