oj.uz

Submission #571059

# Submission time Handle Problem Language Result Execution time Memory
571059 2022-06-01T07:34:17 Z tamthegod Bosses (BOI16_bosses) C++14
100 / 100
 1492 ms 980 KB 
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<stack>
#include<queue>
#include<string>
#include<string.h>
#include<cmath>
#include<vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<cstdio>
#include<bitset>
#include<chrono>
#include<random>
#include<ext/rope>
/* ordered_set
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
*/
#define pb push_back
#define fi first
#define se second
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 5000 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e8;
int n;
vector<int> l[maxN];
vector<int> adj[maxN];
void ReadInput()
{
    cin >> n;
    for(int i=1; i<=n; i++)
    {
        int k;
        cin >> k;
        while(k--)
        {
            int p;
            cin >> p;
            l[p].pb(i);
        }
    }
}
int vis[maxN];
void build(int i)
{
    queue<int> q;
    q.push(i);
    vis[i] = -1;
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        for(int v : l[u])
        {
            if(vis[v]) continue;
            adj[u].pb(v);
            vis[v] = -1;
            q.push(v);
        }
    }
}
int f[maxN];
void dfs(int u)
{
    int s = 0;
    for(int v : adj[u])
    {
        dfs(v);
        s += f[v];
    }
    f[u] = s + 1;
}
int Cal(int i)
{
    for(int i=1; i<=n; i++) adj[i].clear();
    fill(vis, vis + n + 1, 0);
    fill(f, f + n + 1, 0);
    build(i);
    //for(int v : adj[1]) cout << v << " ";return 0;
    dfs(i);
    int res = 0;
    for(int i=1; i<=n; i++)
    {
        res += f[i];
        if(!f[i]) return oo;
    }
    return res;
}
void Solve()
{
    int res = oo;
    for(int i=1; i<=n; i++)
    {
        res = min(res, Cal(i));
    }
    cout << res;
}
int32_t main()
{
    //freopen("x.inp", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ReadInput();
    Solve();
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 5 ms 596 KB Output is correct
13 Correct 5 ms 596 KB Output is correct
14 Correct 360 ms 820 KB Output is correct
15 Correct 35 ms 724 KB Output is correct
16 Correct 1147 ms 856 KB Output is correct
17 Correct 1492 ms 904 KB Output is correct
18 Correct 1475 ms 980 KB Output is correct