oj.uz

Submission #489838

# Submission time Handle Problem Language Result Execution time Memory
489838 2021-11-24T22:12:40 Z ala2 Bosses (BOI16_bosses) C++14
67 / 100
 1028 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;
            while(vv[x][i]||x>n||k>n)
            {
                cout<<"LL";
            }
            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: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:65: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]
   65 |             for(int j=0;j<v[x].size();j++)
      |                         ~^~~~~~~~~~~~
bosses.cpp:80:13: warning: unused variable 'c' [-Wunused-variable]
   80 |         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 2636 KB Output is correct
3 Correct 1 ms 2764 KB Output is correct
4 Correct 2 ms 2784 KB Output is correct
5 Correct 2 ms 2764 KB Output is correct
6 Correct 3 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 2636 KB Output is correct
3 Correct 1 ms 2764 KB Output is correct
4 Correct 2 ms 2784 KB Output is correct
5 Correct 2 ms 2764 KB Output is correct
6 Correct 3 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 2 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 2636 KB Output is correct
3 Correct 1 ms 2764 KB Output is correct
4 Correct 2 ms 2784 KB Output is correct
5 Correct 2 ms 2764 KB Output is correct
6 Correct 3 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 2 ms 4044 KB Output is correct
12 Correct 9 ms 6248 KB Output is correct
13 Correct 7 ms 5196 KB Output is correct
14 Correct 511 ms 247312 KB Output is correct
15 Correct 117 ms 124792 KB Output is correct
16 Runtime error 1028 ms 262148 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -