oj.uz

Submission #571058

# Submission time Handle Problem Language Result Execution time Memory
571058 2022-06-01T07:33:19 Z tamthegod Bosses (BOI16_bosses) C++14
67 / 100
 1500 ms 908 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 par)
{
    int s = 0;
    for(int v : adj[u])
    {
        if(v == par) continue;
        dfs(v, u);
        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, 0);
    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 0 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 0 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
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 0 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 6 ms 616 KB Output is correct
13 Correct 5 ms 596 KB Output is correct
14 Correct 349 ms 852 KB Output is correct
15 Correct 30 ms 724 KB Output is correct
16 Correct 1171 ms 864 KB Output is correct
17 Execution timed out 1521 ms 908 KB Time limit exceeded
18 Halted 0 ms 0 KB -