oj.uz

답안 #570500

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
570500 2022-05-30T09:40:53 Z Huy Bosses (BOI16_bosses) C++17
67 / 100
 1500 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)3e5 + 1;
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 trace[maxN];
int isvis[maxN];
int su[maxN];

void Trace(int v)
{
    isvis[v] = 1;
    int u = trace[v];
    if(u == 0) return;
    adj2[u].push_back(v);
    if(!isvis[u]) Trace(u);
}

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;
        isvis[i] = 0;
        trace[i] = 0;
        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;
                trace[v] = u;
                q.push(v);
            }
        }
    }
    while(!q.empty());

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

    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();
    }
}

/*
4 1
1 1 1 1
1 2
2 3
3 4
*/

Subtask #1
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 436 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #2
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 436 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 448 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 436 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 448 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 596 KB Output is correct
13 Correct 5 ms 596 KB Output is correct
14 Correct 222 ms 944 KB Output is correct
15 Correct 26 ms 744 KB Output is correct
16 Correct 560 ms 964 KB Output is correct
17 Execution timed out 1583 ms 980 KB Time limit exceeded
18 Halted 0 ms 0 KB -