Submission #392780

#	Time	Username	Problem	Language	Result	Execution time	Memory
392780		Iwanttobreakfree	Bosses (BOI16_bosses)	C++17	67 / 100	1570 ms	1308 KiB

bosses

#include <iostream>
#include <vector>
#include <set>
#include <queue>
using namespace std;
long long int cont;
void dfs(int a,int ori,vector<bool>& visto,vector<vector<int> >& v,vector<int>& acumulacion,int parent){
    visto[a]=true;
    for(int x:v[a]){
        if(!visto[x]){
            dfs(x,ori,visto,v,acumulacion,a);
        }
    }
    if(a==ori){
        cont=0;
        for(int i=0;i<visto.size();i++){
            if(!visto[i]){
                cont=1e18;
                return;
            }
            cont+=acumulacion[i];
        }
        return;
    }
    acumulacion[parent]+=acumulacion[a];
}
void bfs(int raiz,vector<set<int> >& v,vector<bool>& visto){
    int n=visto.size();
       queue <int> bfs;
       bfs.push(raiz);
       vector<vector<int> >constbfs(n,vector<int>());
       int nodo;
       visto[raiz]=true;
       while(!bfs.empty()){
       nodo=bfs.front();
       bfs.pop();
        for(auto x:v[nodo]){
                if (!visto[x]){
                    constbfs[nodo].push_back(x);
                    bfs.push(x);
                    visto[x]=true;
                }
            }
        }
        vector<int> acumulacion(n,1);
        vector<bool>nuevo(n,false);
        dfs(raiz,raiz,nuevo,constbfs,acumulacion,raiz);
        return;
}

int main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    int n,k,mini=1e9,a;
    cin>>n;
    vector<set<int> >v (n,set<int>());
    vector<bool>visto;
    for(int i=0;i<n;i++){
        cin>>k;
        while(k--){
            cin>>a;
            a--;
            v[a].insert(i);
        }
    }
    for(int i=0;i<n;i++){
    visto=vector<bool>(n,false);
    bfs(i,v,visto);
    if(mini>cont)mini=cont;
}
    cout<<mini;
}

Compilation message (stderr)

bosses.cpp: In function 'void dfs(int, int, std::vector<bool>&, std::vector<std::vector<int> >&, std::vector<int>&, int)':
bosses.cpp:16:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |         for(int i=0;i<visto.size();i++){
      |                     ~^~~~~~~~~~~~~

• Subtask 1: 22 / 22
• Subtask 2: 45 / 45
• Subtask 3: 0 / 33