Submission #1370580

#TimeUsernameProblemLanguageResultExecution timeMemory
1370580travelerxBosses (BOI16_bosses)C++20
100 / 100
924 ms21196 KiB
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>

#include <vector>
#include <array>
#include <deque>
#include <queue>
#include <stack>
#include <list>

#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>

#include <algorithm>
#include <numeric>
#include <functional>

#include <string>
#include <sstream>

#include <bitset>
#include <tuple>
#include <utility>

#include <random>
#include <chrono>

using namespace std;

#define ll long long
#define ld long double
#define pb push_back
#define pob pop_back
#define pf push_front
#define ins insert
#define lb lower_bound
#define ub upper_bound
#define nd second
#define st first
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vll vector<ll>
#define vpii vector<pair<int, int>>
#define srt(x) sort((x).begin(), (x).end())
#define rst(x, y) fill(x, x + roz, y)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define rep(i, stt, endd) for (int i = stt; i <= endd; i++)

const ll infl = 1e18 + 90;
const int inf = 1e9 + 93;
const int roz = 5e3 + 13;
const int mod = 998244353;
const int logll = 64;
const int logi = 32;
const int stala = (1 << 17);
using spumldidsi = std::set<std::pair<std::unordered_map<long double, std::vector<std::map<int, std::set<long long>>>>, std::deque<std::set<std::pair<long long, std::unordered_map<int, std::vector<double>>>>>>>;
// xddd

vi dzieci[roz];
queue<int> q;
vi graf[roz];
bool odw[roz];
int res[roz];
int suma = 0;

void dfs(int w, int rodz)
{
    int cnt = 0;
    res[w] = 0;
    for (int i : graf[w])
    {
        if (i != rodz)
        {
            dfs(i, w);
            res[w] += res[i];
        }
    }
    res[w]++;
    suma += res[w];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        graf[i].reserve(n);
    for (int i = 1; i <= n; i++)
    {
        int k;
        cin >> k;
        for (int j = 1; j <= k; j++)
        {
            int a;
            cin >> a;
            dzieci[a].pb(i);
        }
    }

    int mini = inf;
    for (int i = 1; i <= n; i++)
    {

        for (int j = 1; j <= n; j++)
        {
            graf[j].clear();
        }
        memset(odw, false, sizeof(odw));

        q.push(i);
        odw[i] = true;
        int kraw = 0;
        while (q.size() > 0)
        {
            int w = q.front();
            q.pop();
            for (int j : dzieci[w])
            {
                if (!odw[j])
                {
                    odw[j] = true;
                    graf[w].pb(j);
                    kraw++;
                    q.push(j);
                }
            }
        }
        if (kraw != n - 1)
        {
            continue;
        }

        suma = 0;
        dfs(i, -1);
        mini = min(mini, suma);
    }

    cout << mini << '\n';

    return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...