oj.uz

Submission #489813

# Submission time Handle Problem Language Result Execution time Memory
489813 2021-11-24T18:54:52 Z ala2 Bosses (BOI16_bosses) C++14
67 / 100
 1052 ms 262148 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<int>v[5050];
int vi[5010][5010];
int d[5050][5050];
vector<int>gr[5050];
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=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:60: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]
   60 |             for(int j=0;j<v[x].size();j++)
      |                         ~^~~~~~~~~~~~
bosses.cpp:74:13: warning: unused variable 'c' [-Wunused-variable]
   74 |         int c=dfs(i,i);
      |             ^

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 588 KB Output is correct
2 Correct 0 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 0 ms 588 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 0 ms 588 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 588 KB Output is correct
2 Correct 0 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 0 ms 588 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 0 ms 588 KB Output is correct
7 Correct 1 ms 1612 KB Output is correct
8 Correct 1 ms 1100 KB Output is correct
9 Correct 1 ms 844 KB Output is correct
10 Correct 1 ms 1740 KB Output is correct
11 Correct 2 ms 1868 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 588 KB Output is correct
2 Correct 0 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 0 ms 588 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 0 ms 588 KB Output is correct
7 Correct 1 ms 1612 KB Output is correct
8 Correct 1 ms 1100 KB Output is correct
9 Correct 1 ms 844 KB Output is correct
10 Correct 1 ms 1740 KB Output is correct
11 Correct 2 ms 1868 KB Output is correct
12 Correct 8 ms 4036 KB Output is correct
13 Correct 6 ms 3148 KB Output is correct
14 Correct 493 ms 245068 KB Output is correct
15 Correct 125 ms 122820 KB Output is correct
16 Runtime error 1052 ms 262148 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -