제출 #1290675

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290675		Gadir_2880	Bosses (BOI16_bosses)	C++20	100 / 100	783 ms	1104 KiB

bosses

//The Rumbling starts here:

#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include<bits/stdc++.h>
#define debug(n,m) cout<<"["<<#n<<"]->"<<n<<m
#define int long long
#define all(x) x.begin(),x.end() 
#define ai array<int,2>
#define vv vector
#define pb push_back
using namespace std;

const int N=3132352;
const int mod=1e9+7;
const int inf=(1ll<<55)-1;

int a[N];
vector<int> tr[N];

int ans[N];

void dfs(int u,int p) {
  //debug(u,' ');
  int cos=1;
  for (int v:tr[u]) {
    if (v!=p) {
      dfs(v,u);
    }
  }
  for (int v:tr[u]) {
    if (v!=p) cos+=ans[v];
  }
    ans[u]=cos;
}

void levi() {
  //#define tests
  int n;
  cin>>n;
  vector<vector<int>> d(n+1,vector<int>());
  ai res={0,1};
  for (int i=1;i<=n;i++) {
    int l;
    cin>>l;
    vector<int> v(l+1);
    for (int j=1;j<=l;j++) {
      cin>>v[j];
      d[v[j]].pb(i);
      if (d[v[j]].size()>res[0]) res={(int)d[v[j]].size(),v[j]};
    }
  } 
  int re=inf;
  for (int i=1;i<=n;i++) {
    res[1]=i;
    for (int j=1;j<=n;j++) {
      ans[j]=0;
      tr[j].clear();
    }
    vector<int> vs(n+1,0);
    queue<int> q;
    vs[res[1]]=1;
    q.push(res[1]);
    while(!q.empty()) {
      int u=q.front();
      q.pop();
      vs[u]=1;
      for (int v:d[u]) {
        if (!vs[v]) {
          vs[v]=1;
          tr[u].pb(v);
          q.push(v);
        }
      }
    }
    bool f=0;
    for (int i=1;i<=n;i++){
      if (!vs[i]) f=1;
    }
    if (f) continue;
    dfs(res[1],-1);
    re=min(re,accumulate(ans+1,ans+n+1,0ll));
  }
  cout<<re<<'\n';
}


int32_t main() {
  //freopen("input.in","r",stdin);
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int tt=1;
  #ifdef tests
  cin>>tt;
  #endif
  while(tt--) levi();
}

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