Submission #531069

#	Time	Username	Problem	Language	Result	Execution time	Memory
531069		Uzouf	Bosses (BOI16_bosses)	C++14	0 / 100	1581 ms	204 KiB

bosses

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
int mod=1e9+7;
const int N=2e5+5;

int n;
vector<vector<int> >v;
vector<vector<int> > grph;
vector<vector<int> > oppg;
vector<bool> vis;
vector<int> cst;
vector<int> dis;

void bfs(int j)
{
  queue<int> q;
  vector<bool> vis(n,false);
  dis=vector<int> (n,1);
  q.push(j); vis[j]=true;
  while (q.size()>0)
  {
    int indx=q.front(); q.pop();
    for (int i=0;i<v[indx].size();i++)
    {
      if (vis[v[indx][i]]==false)
      {
        int nm=v[indx][i]; vis[nm]=true;
        q.push(nm); dis[nm]=dis[indx]+1;
        grph[indx].push_back(nm); oppg[nm].push_back(indx);
      }
    }
  }
}

int add(int indx)
{
  int mx=0;
  for (int i=0;i<n;i++)
  {
    mx=max(mx,dis[i]);
  }
  int nm=0;
  while (mx--)
  {
    for (int i=0;i<n;i++)
    {
      if (grph[i].size()==0) {cst[i]=1;}
      else
      {
        int kds=0;
        for (int j=0;j<grph[i].size();j++)
        {
          kds+=cst[grph[i][j]];
        }
        cst[i]=kds+1;
      }
    }
    nm++;
  }
}


signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin>>n;
    v=vector<vector<int> > (n);
    for (int i=0;i<n;i++)
    {
      int m; cin>>m;
      while (m--)
      {
        int a; cin>>a; a--;
        v[a].push_back(i);
      }
    }

    int ans=INT_MAX,tmp=0;
    for (int i=0;i<n;i++)
    {
      tmp=0;
      grph=vector<vector<int> > (n);
      oppg=vector<vector<int> > (n);
      vis=vector<bool> (n,false);
      cst=vector<int> (n,0);
      bfs(i);
      add(i);
      for (int i=0;i<n;i++)
      {
        tmp+=cst[i];
      }
      ans=min(ans,tmp);
    }
    cout<<ans;
}

Compilation message (stderr)

bosses.cpp: In function 'void bfs(long long int)':
bosses.cpp:25:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for (int i=0;i<v[indx].size();i++)
      |                  ~^~~~~~~~~~~~~~~
bosses.cpp: In function 'long long int add(long long int)':
bosses.cpp:53:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         for (int j=0;j<grph[i].size();j++)
      |                      ~^~~~~~~~~~~~~~~
bosses.cpp:62:1: warning: no return statement in function returning non-void [-Wreturn-type]
   62 | }
      | ^

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