Submission #243681

#	Time	Username	Problem	Language	Result	Execution time	Memory
243681		kimbj0709	Bosses (BOI16_bosses)	C++14	67 / 100	1577 ms	1140 KiB

bosses

#include <bits/stdc++.h>
using namespace std;
#define maxn 5050
vector<vector<int> > adj(maxn);
void dfs(int node,int parent,vector<vector<int> > &ad,vector<int> &dist){
  dist[node] = 1;
  for(auto k:ad[node]){
    if(k!=parent){
      dfs(k,node,ad,dist);
      dist[node] += dist[k];
    }
  }
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);cout.tie(0);
  int no_of_input,no_of_input1,input;
  cin >> no_of_input;
  for(int i=1;i<=no_of_input;i++){
    cin >> no_of_input1;
    for(int j=0;j<no_of_input1;j++){
      cin >> input;
      //adj[i].push_back(input);
      adj[input].push_back(i);
    }
  }
  int ans = INT_MAX;
  deque<pair<int,int> > q1;
  deque<int> q2;
  vector<int> dist(maxn,INT_MAX);
  vector<int> parent(maxn,0);
  vector<int> dist2(maxn,0);
  for(int i=1;i<=no_of_input;i++){//tree rooted at node i
    for(int j=1;j<=no_of_input;j++){
      dist[j] = INT_MAX;
      parent[j] = 0;
      dist2[j] = 1;
    }
    q1.push_back({i,0});
    dist[i] = 0;
    while(q1.size()!=0){
      pair<int,int> a = q1.front();
      q1.pop_front();
      for(auto k:adj[a.first]){
        if(a.second+1<dist[k]){
          dist[k] = a.second+1;
          parent[k] = a.first;
          q1.push_back({k,dist[k]});
        }
      }
    }
    vector<pair<int,int> > vect1;
    for(int j=1;j<=no_of_input;j++){
      vect1.push_back({dist[j],j});
    }
    sort(vect1.begin(),vect1.end());
    reverse(vect1.begin(),vect1.end());
    for(int j=0;j<vect1.size();j++){
      //cout << parent[vect1[j].second] << endl;
      dist2[parent[vect1[j].second]] += dist2[vect1[j].second];
    }
    int sum = 0;
    for(int j=1;j<=no_of_input;j++){
      
      if(i!=j&&parent[j]==0){
        sum = 1000000000;
      }
      //cout << dist2[j] << " ";
      sum += dist2[j];
    }
    //cout << endl;
    //cout << sum << "--\n";
    ans = min(ans,sum);
  }
  cout << ans;
}

Compilation message (stderr)

bosses.cpp: In function 'int32_t main()':
bosses.cpp:58:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0;j<vect1.size();j++){
                 ~^~~~~~~~~~~~~

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