Submission #721436

#	Time	Username	Problem	Language	Result	Execution time	Memory
721436		vjudge1	Bosses (BOI16_bosses)	C++17	67 / 100	1576 ms	872 KiB

bosses

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ld long double
#define ll long long
#define S second
#define F first

using namespace __gnu_pbds;
using namespace std;

typedef tree<long long, null_type, less_equal<long long>,
    rb_tree_tag, tree_order_statistics_node_update> Tree;

const ll INF = 9223372036854775807LL;
const ll inf = 2147483647;
const ll MAXN = 200010;
const ll MOD = 1e9 + 7;
const ld PI = acos(-1);
const ll NROOT = 320; 

ll binpow(ll a, ll b) {
  ll res = 1;
  for (;b; b /= 2, a *= a, a %= MOD)
    if (b & 1) res *= a, res %= MOD;
  return res % MOD;
}

ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a * b / gcd(a, b);}
ll invmod(ll a) {return binpow(a, MOD - 2);}

void dfs(int n, vector<vector<int>> &t, vector<int> &sum, vector<bool> &vis) {
  if (vis[n]) return;
  vis[n] = 1;
  
  for (auto &x : t[n]) {
    dfs(x, t, sum, vis);
    sum[n] += sum[x];
  }
  sum[n] ++;
}

int32_t main () {
  ios_base::sync_with_stdio(false); 
  cin.tie(nullptr);

  int n; cin >> n;

  vector<vector<int>> g(n + 1);

  for (int i = 1; i <= n; i ++) {
    int k; cin >> k;
    while (k --) {
      int x; cin >> x;
      g[x].push_back(i);
    }
  }

  int res = 1e9;
  for (int i = 1; i <= n; i ++) {
    vector<vector<int>> t(n + 1);
    vector<bool> vis(n + 1), vis2(n + 1);

    queue<pair<int ,int>> q;
    q.push({i, 0}); 
    while (!q.empty()) {
      int x = q.front().F;
      int prv = q.front().S;
      q.pop();

      if (vis[x]) continue;
      t[prv].push_back(x);
      vis[x] = 1;

      for (auto &y : g[x]) {
        if (prv != y) 
          q.push({y, x});
      }
    }
    
    vector<int> sum(n + 1);
    dfs(0, t, sum, vis2);

    bool ic = 1;
    for (int j = 1; j <= n; j ++) {
      if (!vis[j]) ic = 0;
    }

    sum[0] = 0;
    for (int j = 1; j <= n; j ++) {
      sum[0] += sum[j];
    } 
    if (!ic) sum[0] = 1e9;

    res = min(res, sum[0]);
  }

  cout << res << '\n';

  return 0;
}

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