oj.uz

Submission #489836

# Submission time Handle Problem Language Result Execution time Memory
489836 2021-11-24T21:24:37 Z ala2 Bosses (BOI16_bosses) C++14
67 / 100
 1012 ms 262148 KB 
#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=1000000000000000;
    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: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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 1 ms 2716 KB Output is correct
3 Correct 1 ms 2764 KB Output is correct
4 Correct 1 ms 2764 KB Output is correct
5 Correct 2 ms 2764 KB Output is correct
6 Correct 2 ms 2764 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 1 ms 2716 KB Output is correct
3 Correct 1 ms 2764 KB Output is correct
4 Correct 1 ms 2764 KB Output is correct
5 Correct 2 ms 2764 KB Output is correct
6 Correct 2 ms 2764 KB Output is correct
7 Correct 2 ms 3660 KB Output is correct
8 Correct 2 ms 3276 KB Output is correct
9 Correct 2 ms 3020 KB Output is correct
10 Correct 2 ms 3916 KB Output is correct
11 Correct 3 ms 4044 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 1 ms 2716 KB Output is correct
3 Correct 1 ms 2764 KB Output is correct
4 Correct 1 ms 2764 KB Output is correct
5 Correct 2 ms 2764 KB Output is correct
6 Correct 2 ms 2764 KB Output is correct
7 Correct 2 ms 3660 KB Output is correct
8 Correct 2 ms 3276 KB Output is correct
9 Correct 2 ms 3020 KB Output is correct
10 Correct 2 ms 3916 KB Output is correct
11 Correct 3 ms 4044 KB Output is correct
12 Correct 9 ms 6220 KB Output is correct
13 Correct 7 ms 5308 KB Output is correct
14 Correct 495 ms 247108 KB Output is correct
15 Correct 124 ms 124684 KB Output is correct
16 Runtime error 1012 ms 262148 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -