oj.uz

Submission #531070

# Submission time Handle Problem Language Result Execution time Memory
531070 2022-02-27T15:41:37 Z Uzouf Bosses (BOI16_bosses) C++14
0 / 100
 1500 ms 204 KB 
#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;
bool bl=true;

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

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);
      bl=true;
      bfs(i);
      if (bl==false) {continue;}
      add(i);
      for (int i=0;i<n;i++)
      {
        tmp+=cst[i];
      }
      ans=min(ans,tmp);
    }
    cout<<ans;
}

Compilation message

bosses.cpp: In function 'void bfs(long long int)':
bosses.cpp:26: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]
   26 |     for (int i=0;i<v[indx].size();i++)
      |                  ~^~~~~~~~~~~~~~~
bosses.cpp: In function 'long long int add(long long int)':
bosses.cpp:58: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]
   58 |         for (int j=0;j<grph[i].size();j++)
      |                      ~^~~~~~~~~~~~~~~
bosses.cpp:67:1: warning: no return statement in function returning non-void [-Wreturn-type]
   67 | }
      | ^

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1581 ms 204 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1581 ms 204 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1581 ms 204 KB Time limit exceeded
2 Halted 0 ms 0 KB -