제출 #695177

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
695177		Mr_Ph	Bosses (BOI16_bosses)	C++14	0 / 100	1 ms	212 KiB

bosses

///Never gonna give you up.
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
typedef long long int lli;
typedef unsigned long long ull;
using namespace std;
using namespace __gnu_pbds;
template<class x>
using ordered_set = tree<x, null_type,less<x>, rb_tree_tag,tree_order_statistics_node_update>;
const ll mod=(ll)1e9+7;
const ll mod1=998244353;
///the defines :)
#define endl '\n'
#define vi vector<int>
#define vll vector<ll>
#define ent(arr) for(int i=0;i<arr.size();i++)cin>>arr[i];
#define all(arr) arr.begin(),arr.end()
#define allr(arr) arr.rbegin(),arr.rend()
#define sz size()
#define int long long
///the end of the defines ;)
int n;
vector<vector<int>>padj;
vector<vector<int>>adj;
map<int,int>val;
map<int,int>val1;
bool valid=false;
vector<vector<int>>build(int node)
{
  vector<vector<int>>yay(n+1);
  map<int,int>mp;
  queue<int>q;
  q.push(node);
  while(q.sz)
  {
    mp[q.front()]++;
    for(auto i:padj[q.front()])
    {
      if(!mp[i])
      {
        yay[q.front()].push_back(i);
        mp[i]++;
         q.push(i);
      }
    }
    q.pop();
  }
  for(int i=1;i<=n;i++)
    if(!mp[i])valid=true;
  return yay;
}
int hello=0;
void dfs(int node)
{
  val[node]=1;
  for(auto i:adj[node])
  {
    dfs(i);
    val[node]+=val[i];
  }
}
void preprocess(){}
void solve()
{
  cin>>n;
  padj.resize(n+1);
  adj.resize(n+1);
  for(int i=0;i<n;i++)
  {
    int x;
    cin>>x;
    for(int j=0;j<x;j++)
    {
      int a;
      cin>>a;
      padj[a].push_back(i+1);
    }
  }
  int ans=LONG_MAX;
  for(int i=1;i<=n;i++)
  {
    val=val1;
    adj=build(i);
    if(valid)continue;
    hello=0;
    dfs(i);
    for(int j=1;j<=n;j++)hello+=val[j];
    ans=min(ans,hello);
  }
  cout<<ans<<endl;
}
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    preprocess();
    //bla();
    int t=1;
   //cin>>t;
    while(t--)
        solve();
}

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