Submission #1037295

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037295		vjudge1	Bosses (BOI16_bosses)	C++17	100 / 100	989 ms	1116 KiB

bosses

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define pb push_back
#define pf push_front
#define fi first
#define se second
const ll mod = 1e9+7, mxn = 5e3+7;
vector<vector<ll>> g(mxn), gg(mxn);
ll n, dp[mxn], pr[mxn];
bool vis[mxn];
void dfs(ll u) {for (ll i : gg[u]) {dfs(i); dp[u] += dp[i];}}
ll solve(ll s)
{
    queue<ll> q; q.push(s); 
    memset(vis,0,sizeof(vis));
    vis[s] = 1; pr[s] = 0;
    while (!q.empty()) 
    {
        ll u = q.front(); q.pop();
        for (ll i : g[u]) if (!vis[i])
        {
            vis[i] = 1; q.push(i);
            pr[i] = u;
        } 
    } 
    for (ll i = 1; i <= n; i++) 
    {
        dp[i] = 1; gg[i].clear();
        if (!vis[i]) return -1;
    }
    for (ll i = 1; i <= n; i++) if (pr[i]) gg[pr[i]].pb(i);
    dfs(s);
    ll ans = 0;
    for (ll i = 1; i <= n; i++) ans += dp[i];
    return ans;
}
signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    // freopen("test.inp","r",stdin); freopen("test.out","w",stdout); freopen("test.err","w",stderr);
    cin >> n;
    for (ll i = 1; i <= n; i++)
    {
        ll k; cin >> k;
        while (k--)
        {
            ll x; cin >> x;
            g[x].pb(i);
        }
    }
    ll ans = 1e18;
    for (ll i = 1; i <= n; i++) 
    {
        ll c = solve(i);
        if (c != -1) ans = min(ans, c);
    } 
    cout << ans;
}

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