oj.uz

Submission #489811

# Submission time Handle Problem Language Result Execution time Memory
489811 2021-11-24T18:51:15 Z ala2 Bosses (BOI16_bosses) C++14
67 / 100
 9 ms 4044 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<int>v[1010];
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]){
            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 460 KB Output is correct
2 Correct 0 ms 460 KB Output is correct
3 Correct 0 ms 460 KB Output is correct
4 Correct 0 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 460 KB Output is correct
2 Correct 0 ms 460 KB Output is correct
3 Correct 0 ms 460 KB Output is correct
4 Correct 0 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 1484 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 460 KB Output is correct
2 Correct 0 ms 460 KB Output is correct
3 Correct 0 ms 460 KB Output is correct
4 Correct 0 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 1484 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 9 ms 4044 KB Output is correct
13 Correct 7 ms 3012 KB Output is correct
14 Runtime error 9 ms 588 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -