Submission #98958

#	Time	Username	Problem	Language	Result	Execution time	Memory
98958		zicon35	Bosses (BOI16_bosses)	C++14	0 / 100	2 ms	384 KiB

bosses

#include<bits/stdc++.h>

using namespace std;

int n,k,v;
vector< vector<int>> adj;
int ans=1e9;
map<int,int> vis;
set<int> seen;

void dfs(int u,int d,int & sum,int n){
    if(vis[u]){
        return;
    }
    //cout<<"u: "<<u<<d<<sum<<endl;
    vis[u] = 1;
    seen.insert(u);
    for(int i=0;i<adj[u].size();i++){
        int to  = adj[u][i];
        if(!vis[to]){
            sum += d;
            //cout<<"test"<<endl;
            dfs(to,d+1,sum,n);
        }
    }

    if(seen.size()==n){
        //cout<<"here"<<sum+d<<endl;
        ans = min(ans,sum+d);
        seen.clear();
        return;
    }
}

long long  solve(int n){
    cin>>n;
    adj.resize(n+2);
    for(int i=1;i<=n;i++){
       cin>>k;
       for(int j=1;j<=k;j++){
            cin>>v;
            adj[v].push_back(i);
       } 
    }

    for(int i=1;i<=n;i++){
        int sum = 1;
        vis.clear();
        seen.clear();
        dfs(i,1,sum,n);
    }
    return ans;
}

int main(){

    cout<<solve(n)<<endl;
    return 0;
}

Compilation message (stderr)

bosses.cpp: In function 'void dfs(int, int, int&, int)':
bosses.cpp:18:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<adj[u].size();i++){
                 ~^~~~~~~~~~~~~~
bosses.cpp:27:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(seen.size()==n){
        ~~~~~~~~~~~^~~

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