Submission #951439

#	Time	Username	Problem	Language	Result	Execution time	Memory
951439		Zena_Hossam	Bosses (BOI16_bosses)	C++14	0 / 100	0 ms	344 KiB

bosses

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define ll int
using namespace std;
namespace __gnu_pbds
{
typedef tree<ll,
        null_type,
        less_equal<ll>,
        rb_tree_tag,
        tree_order_statistics_node_update> ordered_set;
}
using namespace __gnu_pbds;
#define fi ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//#define ll double

#define ll1 long long
#define F first
#define S second
#define sz size()
#define all(s) s.begin(),s.end()
#define all1(s) s.rbegin(),s.rend()
map<ll,ll>m;
vector<vector<ll>>v;
ll c=1e9;
void solve(ll idx)
{
    if(m[idx])return;//cout<<idx<<" ";
    ll g=0;//cout<<idx<<"\n";
    for(ll i=0; i<v[idx].size(); i++)
    {
        // cout<<idx<<" "<<v[idx][i]<<"\n";
        solve(v[idx][i]);
        g+=(m[v[idx][i]]);
    }

    m[idx]=g+1;
    // cout<<idx<<" "<<m[idx]<<"\n";
    return;
}
ll ch(ll idx,ll arr[])
{
    if(arr[idx])return 0;
    arr[idx]=1;
    for(ll  i=0; i<v[idx].size(); i++)
    {
        if(!ch(v[idx][i],arr))return 0;
    }
    return 1;
}
int main()
{
    fi
    //freopen("stdin.in","r",stdin);freopen("stdout.out","w",stdout);
    //cin>>T;ll oo=0;
    ll n;
    cin>>n;
    vector<ll>s[n+5];
    ll a[n+5]= {};
    v.resize(n+5);
    for(ll i=0; i<n; i++)
    {
        ll m;
        cin>>m;
        for(ll j=0; j<m; j++)
        {
            ll o;
            cin>>o;
            s[o].push_back(i+1);
        }
    }
    ll jdx,mnn=0;
    for(ll i=1; i<=n; i++)
    {
        queue<ll>q;
        ll ss=0;
        q.push(i);
        ll aa[n+5]= {};
        ll k2=0;
        ll  io=0;
        while(q.size())
        {
            k2++;
            ll a1=q.front();
            q.pop();
            // cout<<a1<<"\n";
            aa[a1]=1;
            for(ll j=0; j<s[a1].sz; j++)
            {
                ll o[n+5]= {};
                if(aa[s[a1][j]]==0)
                {
                    aa[s[a1][j]]=1;
                    io++;
                    v[a1].push_back(s[a1][j]);
                    q.push(s[a1][j]);
                }
            }
        }
        if(mnn<io&&k2==n)
        {
            mnn=io;
            jdx=i;
        }
        for(ll i=1; i<=n; i++)
            v[i].clear();
        m.clear();
    }
    queue<ll>q;
    ll i=jdx;
    ll ss=0;
    q.push(i);
    ll aa[n+5]= {};
    ll k2=0;
    ll  io=0;
    while(q.size())
    {
        k2++;
        ll a1=q.front();
        q.pop();
        // cout<<a1<<"\n";
        aa[a1]=1;
        for(ll j=0; j<s[a1].sz; j++)
        {
            ll o[n+5]= {};
            if(aa[s[a1][j]]==0)
            {
                aa[s[a1][j]]=1;
                io++;
                v[a1].push_back(s[a1][j]);
                q.push(s[a1][j]);
            }
        }
    }
    for(ll ii=1; ii<=n; ii++)
    {

        if(!m[ii])
            solve(ii);
        ss+=m[ii];
    }
    cout<<c;
}

Compilation message (stderr)

bosses.cpp: In function 'void solve(int)':
bosses.cpp:31:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for(ll i=0; i<v[idx].size(); i++)
      |                 ~^~~~~~~~~~~~~~
bosses.cpp: In function 'int ch(int, int*)':
bosses.cpp:46:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for(ll  i=0; i<v[idx].size(); i++)
      |                  ~^~~~~~~~~~~~~~
bosses.cpp: In function 'int main()':
bosses.cpp:89:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |             for(ll j=0; j<s[a1].sz; j++)
      |                          ^
bosses.cpp:91:20: warning: unused variable 'o' [-Wunused-variable]
   91 |                 ll o[n+5]= {};
      |                    ^
bosses.cpp:77:12: warning: unused variable 'ss' [-Wunused-variable]
   77 |         ll ss=0;
      |            ^~
bosses.cpp:124:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |         for(ll j=0; j<s[a1].sz; j++)
      |                      ^
bosses.cpp:126:16: warning: unused variable 'o' [-Wunused-variable]
  126 |             ll o[n+5]= {};
      |                ^
bosses.cpp:60:8: warning: unused variable 'a' [-Wunused-variable]
   60 |     ll a[n+5]= {};
      |        ^

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