oj.uz

Submission #489818

# Submission time Handle Problem Language Result Execution time Memory
489818 2021-11-24T20:29:21 Z ala2 Bosses (BOI16_bosses) C++14
67 / 100
 1054 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;
            while(x>n)
            {
                
            }
            if(vv[x][i])
            {
                 while(1)
                 {
                     
                 }
            }
            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:71: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]
   71 |             for(int j=0;j<v[x].size();j++)
      |                         ~^~~~~~~~~~~~
bosses.cpp:85:13: warning: unused variable 'c' [-Wunused-variable]
   85 |         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 0 ms 588 KB Output is correct
4 Correct 0 ms 588 KB Output is correct
5 Correct 0 ms 588 KB Output is correct
6 Correct 1 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 0 ms 588 KB Output is correct
4 Correct 0 ms 588 KB Output is correct
5 Correct 0 ms 588 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 1632 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 0 ms 588 KB Output is correct
4 Correct 0 ms 588 KB Output is correct
5 Correct 0 ms 588 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 1632 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 4128 KB Output is correct
13 Correct 6 ms 3160 KB Output is correct
14 Correct 511 ms 245032 KB Output is correct
15 Correct 127 ms 122676 KB Output is correct
16 Runtime error 1054 ms 262148 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -