#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;
}
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=1e18;
for(ll i=1; i<=n; i++)
{
queue<pair<ll,ll>>q;
ll ss=0;
q.push({i,0});
ll aa[n+5]= {};
ll k2=0;
ll iio=0;
while(q.size())
{
k2++;
pair<ll,ll>aa1=q.front();
ll a1=aa1.first,b1=aa1.second;
q.pop();ll io=0;
aa[a1]=1;iio+=b1;
for(ll j=0; j<s[a1].sz; j++)
{
if(aa[s[a1][j]]==0)
{
aa[s[a1][j]]=1;
q.push({s[a1][j],b1+1});
}
}
}
if(mnn>iio&&k2==n)
{
mnn=iio;
jdx=i;
}
}
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())
{
ll a1=q.front();
q.pop();
// cout<<a1<<"\n";
aa[a1]=1;
for(ll j=0; j<s[a1].sz; j++)
{
if(aa[s[a1][j]]==0)
{
aa[s[a1][j]]=1;
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<<ss;
}
Compilation message
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 main()':
bosses.cpp:63:16: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
63 | ll jdx,mnn=1e18;
| ^~~~
bosses.cpp:79:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | for(ll j=0; j<s[a1].sz; j++)
| ^
bosses.cpp:77:24: warning: unused variable 'io' [-Wunused-variable]
77 | q.pop();ll io=0;
| ^~
bosses.cpp:67:12: warning: unused variable 'ss' [-Wunused-variable]
67 | ll ss=0;
| ^~
bosses.cpp:107:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
107 | for(ll j=0; j<s[a1].sz; j++)
| ^
bosses.cpp:50:8: warning: unused variable 'a' [-Wunused-variable]
50 | ll a[n+5]= {};
| ^
bosses.cpp:99:8: warning: unused variable 'k2' [-Wunused-variable]
99 | ll k2=0;
| ^~
bosses.cpp:100:9: warning: unused variable 'io' [-Wunused-variable]
100 | ll io=0;
| ^~
bosses.cpp:63:8: warning: 'jdx' may be used uninitialized in this function [-Wmaybe-uninitialized]
63 | ll jdx,mnn=1e18;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
344 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
1 ms |
348 KB |
Output is correct |
| 11 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
344 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
1 ms |
348 KB |
Output is correct |
| 11 |
Correct |
1 ms |
348 KB |
Output is correct |
| 12 |
Correct |
4 ms |
348 KB |
Output is correct |
| 13 |
Correct |
3 ms |
584 KB |
Output is correct |
| 14 |
Correct |
109 ms |
1088 KB |
Output is correct |
| 15 |
Correct |
5 ms |
1116 KB |
Output is correct |
| 16 |
Correct |
462 ms |
1164 KB |
Output is correct |
| 17 |
Correct |
441 ms |
1192 KB |
Output is correct |
| 18 |
Correct |
459 ms |
1104 KB |
Output is correct |
