Submission #489839

#	Time	Username	Problem	Language	Result	Execution time	Memory
489839		ala2	Bosses (BOI16_bosses)	C++14	67 / 100	1039 ms	262148 KiB

bosses

#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<int>v[50500];
int vi[5010][5010];
int d[5050][5050];
vector<int>gr[50500];
int vv[5050][5050];
int dfs(int node,int i)
{
    
    if(d[i][node])
        return d[i][node];
    if(gr[node].size()==0)
    {
        return d[i][node]=1;;
    }
    int sum=0;
    for(int u=0;u<gr[node].size();u++)
    {
         sum+=dfs(gr[node][u],i);
    }
    return d[i][node]=sum+1;
}
signed main()
{
//    memset(gr,0,sizeof gr);
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int k;
        cin>>k;
        for(int j=0;j<k;j++)
        {
            
            int x;
            cin>>x;
            if(!vv[x][i]&&x<=n){
            v[x].push_back(i+1);
            vv[x][i]=1;
            }
 
        }
    }
    int mn=10000000000;
    for(int i=1;i<n+1;i++)
    {
        //cout<<"_______________________"<<endl;
        for(int uu=0;uu<=n;uu++)
        {
            gr[uu].clear();
        }
        queue<int>q;
        q.push(i);
        vi[i][i]=1;
        while(!q.empty())
        {
            int x=q.front();
            q.pop();
            for(int j=0;j<v[x].size();j++)
            {
                int h=v[x][j];
                if(!vi[i][h])
                {
                    vi[i][h]=1;
                    q.push(h);
                  //  cout<<"                "<<i<<"  "<<h<<endl;
                    gr[x].push_back(h);
                }
            }
        }
        
        
        if(v[i].size())
        int c=dfs(i,i);
        int yy=0; int bb=0;
        for(int j=1;j<=n;j++)
        {
          // // cout<<"       "<<i<<"    "<<j<<"      "<<d[i][j]<<endl;
            yy+=d[i][j];
            if(d[i][j]==0)
                bb=1;
        }
        if(bb)
            continue;
       // cout<<"             "<<i<<"   "<<yy<<endl;
        mn=min(mn,yy);
 
 
    }
    cout<<mn<<endl;
}

Compilation message (stderr)

bosses.cpp: In function 'long long int dfs(long long int, long long int)':
bosses.cpp:19:18: 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]
   19 |     for(int u=0;u<gr[node].size();u++)
      |                 ~^~~~~~~~~~~~~~~~
bosses.cpp: In function 'int main()':
bosses.cpp:61:26: 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]
   61 |             for(int j=0;j<v[x].size();j++)
      |                         ~^~~~~~~~~~~~
bosses.cpp:76:13: warning: unused variable 'c' [-Wunused-variable]
   76 |         int c=dfs(i,i);
      |             ^

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