Submission #489777

#	Time	Username	Problem	Language	Result	Execution time	Memory
489777		ala2	Bosses (BOI16_bosses)	C++14	0 / 100	13 ms	23940 KiB

bosses

#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<int>v[1001000];
int vi[5010][5010];
int d[5050][5050];
vector<int>gr[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;
            v[x].push_back(i+1);

        }
    }
    int mn=1000000000;
    for(int i=1;i<n+1;i++)
    {
        //cout<<"_______________________"<<endl;
        memset(gr,0,sizeof gr);
        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);
                }
            }
        }

        int c=dfs(i,i);
        int yy=0;
        for(int j=1;j<=n;j++)
        {
            yy+=d[i][j];
        }
        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:18: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]
   18 |     for(int u=0;u<gr[node].size();u++)
      |                 ~^~~~~~~~~~~~~~~~
bosses.cpp: In function 'int main()':
bosses.cpp:26:26: warning: 'void* memset(void*, int, size_t)' clearing an object of type 'class std::vector<long long int>' with no trivial copy-assignment; use assignment or value-initialization instead [-Wclass-memaccess]
   26 |     memset(gr,0,sizeof gr);
      |                          ^
In file included from /usr/include/c++/10/vector:67,
                 from /usr/include/c++/10/queue:61,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:86,
                 from bosses.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:389:11: note: 'class std::vector<long long int>' declared here
  389 |     class vector : protected _Vector_base<_Tp, _Alloc>
      |           ^~~~~~
bosses.cpp:45:30: warning: 'void* memset(void*, int, size_t)' clearing an object of type 'class std::vector<long long int>' with no trivial copy-assignment; use assignment or value-initialization instead [-Wclass-memaccess]
   45 |         memset(gr,0,sizeof gr);
      |                              ^
In file included from /usr/include/c++/10/vector:67,
                 from /usr/include/c++/10/queue:61,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:86,
                 from bosses.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:389:11: note: 'class std::vector<long long int>' declared here
  389 |     class vector : protected _Vector_base<_Tp, _Alloc>
      |           ^~~~~~
bosses.cpp:53: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]
   53 |             for(int j=0;j<v[x].size();j++)
      |                         ~^~~~~~~~~~~~
bosses.cpp:66:13: warning: unused variable 'c' [-Wunused-variable]
   66 |         int c=dfs(i,i);
      |             ^

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