Submission #68901

#	Time	Username	Problem	Language	Result	Execution time	Memory
68901		Vahan	Bosses (BOI16_bosses)	C++17	67 / 100	1567 ms	1928 KiB

bosses

#include<iostream>
#include<vector>
#include<deque>
using namespace std;
vector<int> r[20000],g[20000];
deque<int> q;
int n,pp,u[100000],pat=-1;
int dfs(int v,int p)
{
    int x=1;
    for(int i=0;i<r[v].size();i++)
    {
        int to=r[v][i];
        if(to==p)
            continue;
        x+=dfs(to,v);
    }
    pp+=x;
    return x;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int a;
        cin>>a;
        for(int j=1;j<=a;j++)
        {
            int b;
            cin>>b;
            if(i!=b)
                g[b].push_back(i);
        }
    }
    for(int i=1;i<=n;i++)
    {
        q.push_back(i);
        u[i]=1;
        int t=0;
        while(!q.empty())
        {
            int v=q.front();
            q.pop_front();

            t++;
            for(int j=0;j<g[v].size();j++)
            {
                int to=g[v][j];
                if(u[to]==0)
                {
                    u[to]=1;
                    q.push_back(to);
                    r[v].push_back(to);
                }
            }
        }
        q.clear();
        if(t==n)
        {
            pp=0;
            dfs(i,-1);
            if(pp<pat || pat==-1)
                pat=pp;
        }
        for(int j=1;j<=n;j++)
        {
            u[j]=0;
            r[j].clear();
        }
    }
    cout<<pat<<endl;
    return 0;
}

Compilation message (stderr)

bosses.cpp: In function 'int dfs(int, int)':
bosses.cpp:11:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<r[v].size();i++)
                 ~^~~~~~~~~~~~
bosses.cpp: In function 'int main()':
bosses.cpp:47:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j=0;j<g[v].size();j++)
                         ~^~~~~~~~~~~~

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