Submission #158984

#	Time	Username	Problem	Language	Result	Execution time	Memory
158984		InfiniteJest	Bosses (BOI16_bosses)	C++14	67 / 100	1544 ms	1016 KiB

bosses

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <math.h>
#include <map>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;

ifstream in("input.txt");
ofstream out("output.txt");

typedef long long ll;

int n;
vector<int> nodi[5001];
vector<int> p[5001];
bool vis[5001];
int minn=1e9;
int val[5001];
int f;

void bfs(int k){
  queue<int> q;
  q.push(k);
  vis[k]=1;
  while(!q.empty()){
    int cur=q.front();
    f++;
    q.pop();
    for(int i=0;i<nodi[cur].size();i++){
      if(vis[nodi[cur][i]])continue;
      vis[nodi[cur][i]]=1;
      p[cur].pb(nodi[cur][i]);
      q.push(nodi[cur][i]);
    }
  }
}

int dfs(int k){
  int sum=0;
  for(int i=0;i<p[k].size();i++)sum+=dfs(p[k][i]);
  val[k]=sum+1;
  return val[k];
}


int main(){
  cin>>n;
  for(int i=0;i<n;i++){
    int k; cin>>k;
    for(int y=0;y<k;y++){
      int a; cin>>a;
      nodi[a-1].pb(i);
    }
  }
  for(int i=0;i<n;i++){
    for(int y=0;y<n;y++){
      p[y].clear();
      vis[y]=0;
      val[y]=0;
    }
    f=0;
    bfs(i);
    if(f!=n)continue;
    dfs(i);
    int sum=0;
    for(int y=0;y<n;y++)sum+=val[y];
    minn=min(minn,sum);
    //cout<<"i "<<i<<" v "<<sum<<endl;
  }
  cout<<minn;
}

Compilation message (stderr)

bosses.cpp: In function 'void bfs(int)':
bosses.cpp:35:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<nodi[cur].size();i++){
                 ~^~~~~~~~~~~~~~~~~
bosses.cpp: In function 'int dfs(int)':
bosses.cpp:46:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<p[k].size();i++)sum+=dfs(p[k][i]);
               ~^~~~~~~~~~~~

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