oj.uz

Submission #570503

# Submission time Handle Problem Language Result Execution time Memory
570503 2022-05-30T09:44:38 Z Huy Bosses (BOI16_bosses) C++17
100 / 100
 1402 ms 980 KB 
#include<bits/stdc++.h>
//#define int long long
#define pii pair<int,int>
#define fi first
#define se second

using namespace std;
using ll = long long;
using ldb = long double;
const int N = (int)1e8;
const int maxN = (int)5e3 + 5;
const int mod = 1e9 + 7;

void InputFile()
{
    //freopen("scrivener.inp","r",stdin);
    //freopen("scrivener.out","w",stdout);
    //freopen("test.out","r",stdin);
}

void FastInput()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
}

int n;
vector<vector<int>> adj1;
vector<int> adj2[5005];
int res = mod;
int check = 0;

void Read()
{
    cin >> n;
    adj1.resize(n+1);
    for(int i = 1;i <= n;i++)
    {
        int k;
        cin >> k;
        for(int j = 1;j <= k;j++)
        {
            int t;
            cin >> t;
            adj1[t].push_back(i);
        }

    }
}

int dp[maxN];
int su[maxN];

void DFS(int u)
{
    su[u] = 1;
    for(int v : adj2[u])
    {
        DFS(v);
        su[u] += su[v];
    }
    check += su[u];
}

void BFS(int sta)
{
    for(int i = 1;i <= n;i++)
    {
        dp[i] = mod;
        adj2[i].clear();
    }
    dp[sta] = 0;
    queue<int> q;
    q.push(sta);

    do
    {
        int u = q.front();
        q.pop();
        for(int v : adj1[u])
        {
            if(dp[v] > dp[u] + 1)
            {
                dp[v] = dp[u] + 1;
                adj2[u].push_back(v);
                q.push(v);
            }
        }
    }
    while(!q.empty());

    for(int i = 1;i <= n;i++)
    {
        if(dp[i] >= mod) return;
    }

    check = 0;
    DFS(sta);
    res = min(res,check);
}

void Solve()
{
    for(int i = 1;i <= n;i++)
        BFS(i);
    cout << res;
}

void Debug()
{
    //Main_sub();
    //Naive();
}


int32_t main()
{
    FastInput();
    //InputFile();
    //int sub_type;
    //cin >> sub_type;
    //Sieve();
    int test;
    //cin >> test;
    test = 1;
    while(test--)
        //for(int prc = 1; prc <= test; prc++)
    {
        Read();
        Solve();
        //Debug();
    }
}

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 6 ms 468 KB Output is correct
13 Correct 4 ms 468 KB Output is correct
14 Correct 221 ms 848 KB Output is correct
15 Correct 21 ms 744 KB Output is correct
16 Correct 705 ms 848 KB Output is correct
17 Correct 1402 ms 900 KB Output is correct
18 Correct 1361 ms 980 KB Output is correct