Submission #42397

#	Time	Username	Problem	Language	Result	Execution time	Memory
42397		XmtosX	Bosses (BOI16_bosses)	C++14	67 / 100	1536 ms	1260 KiB

bosses

#include <bits/stdc++.h>
using namespace std;
int n,k,lvl[5004],ans,sz[5004],cnt,cur;
vector <int> v1[5004],v[5004];
void bfs (int x)
{
    queue <int> q;
    memset(lvl,0,sizeof lvl);
    lvl[x]=1;
    for (int i=1;i<=n;i++)
        v1[i].clear();
    q.push(x);
    cnt=0;
    while (!q.empty())
    {
        int a= (q.front());
        q.pop();
        cnt++;
        for (int i=0;i<v[a].size();i++)
        {
            if (!lvl[v[a][i]])
            {
                v1[a].push_back(v[a][i]);
                q.push(v[a][i]);
                lvl[v[a][i]]=lvl[a]+1;
            }
        }
    }
}
void dfs (int x)
{
    sz[x]=1;
    for (int i=0;i<v1[x].size();i++)
    {
        dfs(v1[x][i]);
        sz[x]+=sz[v1[x][i]];
    }
    cur+=sz[x];
}
int main()
{
    cin >>n;
    for (int i=1;i<=n;i++)
    {
        cin >>k;
        for (int j=0;j<k;j++)
        {
            int a;
            cin >>a;
            v[a].push_back(i);
        }
    }
    ans=1e9;
    for (int i=1;i<=n;i++)
    {
        bfs(i);
        if (cnt==n)
        {
            cur=0;
            dfs(i);
            ans=min(ans,cur);
        }
    }
    cout<<ans;
    return 0;
}

Compilation message (stderr)

bosses.cpp: In function 'void bfs(int)':
bosses.cpp:19:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i=0;i<v[a].size();i++)
                       ^
bosses.cpp: In function 'void dfs(int)':
bosses.cpp:33:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<v1[x].size();i++)
                   ^

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