oj.uz

Submission #489810

# Submission time Handle Problem Language Result Execution time Memory
489810 2021-11-24T18:47:38 Z ala2 Bosses (BOI16_bosses) C++14
67 / 100
 1102 ms 262148 KB 
#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=100000000000000000;
    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);
                }
            }
        }
        

        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

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:56: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]
   56 |             for(int j=0;j<v[x].size();j++)
      |                         ~^~~~~~~~~~~~
bosses.cpp:70:13: warning: unused variable 'c' [-Wunused-variable]
   70 |         int c=dfs(i,i);
      |             ^

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23884 KB Output is correct
2 Correct 12 ms 23936 KB Output is correct
3 Correct 12 ms 23960 KB Output is correct
4 Correct 13 ms 23892 KB Output is correct
5 Correct 13 ms 23884 KB Output is correct
6 Correct 12 ms 23916 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23884 KB Output is correct
2 Correct 12 ms 23936 KB Output is correct
3 Correct 12 ms 23960 KB Output is correct
4 Correct 13 ms 23892 KB Output is correct
5 Correct 13 ms 23884 KB Output is correct
6 Correct 12 ms 23916 KB Output is correct
7 Correct 17 ms 24852 KB Output is correct
8 Correct 13 ms 24332 KB Output is correct
9 Correct 13 ms 24140 KB Output is correct
10 Correct 14 ms 24840 KB Output is correct
11 Correct 14 ms 24808 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23884 KB Output is correct
2 Correct 12 ms 23936 KB Output is correct
3 Correct 12 ms 23960 KB Output is correct
4 Correct 13 ms 23892 KB Output is correct
5 Correct 13 ms 23884 KB Output is correct
6 Correct 12 ms 23916 KB Output is correct
7 Correct 17 ms 24852 KB Output is correct
8 Correct 13 ms 24332 KB Output is correct
9 Correct 13 ms 24140 KB Output is correct
10 Correct 14 ms 24840 KB Output is correct
11 Correct 14 ms 24808 KB Output is correct
12 Correct 20 ms 26444 KB Output is correct
13 Correct 18 ms 25768 KB Output is correct
14 Correct 525 ms 249460 KB Output is correct
15 Correct 123 ms 127300 KB Output is correct
16 Runtime error 1102 ms 262148 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -