oj.uz

Submission #985362

# Submission time Handle Problem Language Result Execution time Memory
985362 2024-05-17T16:46:48 Z Octa_pe_info Bosses (BOI16_bosses) C++14
0 / 100
 0 ms 348 KB 
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<vector<int>>tabel;
vector<bool>viz;
vector<int>pasi;

int cnt=0,stot=0;

void bfs(int nod){

    queue<int>q;
    viz[nod]=1;
    q.push(nod);
    pasi[nod]=0;
    while(!q.empty()){

        int curent=q.front();
        q.pop();
        for(auto i : tabel[curent])
            if(!viz[i]){

                viz[i]=1;
                pasi[i]=pasi[curent]+1;
                q.push(i);
                cnt++;

            }

    }

}

int dfs(int nod){

   int sal=1;
   for(auto i : tabel[nod])
        if(pasi[i]-1==pasi[nod])
            sal+=dfs(i);
   stot+=sal;
   return sal;

}

int main()
{

    int n;
    cin>>n;

    tabel.resize(n+1);

    for(int i=1;i<=n;i++){

        int k;
        cin>>k;
        for(int j=1;j<=k;j++){
            int x;
            cin>>x;
            tabel[x].push_back(i);
        }

    }
    int salmin=1e9;
    for(int i=1;i<=n;i++){
        viz.resize(n+1,0);
        pasi.resize(n+1,0);
        cnt=0;
        bfs(i);

        if(cnt==n-1){
            stot=0;
            int aux=dfs(i);
            salmin=min(salmin,stot);
        }

    }
    cout<<salmin;
    return 0;
}

Compilation message

bosses.cpp: In function 'int main()':
bosses.cpp:74:17: warning: unused variable 'aux' [-Wunused-variable]
   74 |             int aux=dfs(i);
      |                 ^~~

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -