oj.uz

Submission #711748

# Submission time Handle Problem Language Result Execution time Memory
711748 2023-03-17T12:09:04 Z aedmhsn Bosses (BOI16_bosses) C++17
0 / 100
 2 ms 360 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define A first
#define B second
#define MP make_pair
#define ms(a, x) memset(a, x, sizeof(a)) 
 
#define boost() ios_base::sync_with_stdio(false); cin.tie(NULL)
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long double, long double> pld;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1);

const int mxN=5e3+5;

bool cool[mxN][mxN];

bool vis[mxN];

ll temp=0;

ll dfs(int node){
    ll sum=0;
    vis[node]=1;
    vector <int> children;
    for(int i=1; i<=5000; i++){
        if(cool[node][i] && !vis[i]){
            vis[i]=1;
            children.push_back(i);
        }
    }
    for(auto x:children){
        sum += dfs(x);
    }
    temp += sum+1;
    return sum+1;
}

int main(){ 

    boost();
    int n;
    cin >> n;
    for(int i=1; i<=n; i++){
        int q;
        cin >> q;
        while(q--){
            int x;
            cin >> x;
            cool[x][i]=1;
        }
    }
    ll ans=INT_MAX;
    for(int i=1; i<=n; i++){
        ms(vis, 0);
        temp=0;
        dfs(i);
        ans = min(ans, temp);
    }
    cout << ans;

}

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 360 KB Output is correct
3 Incorrect 2 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 360 KB Output is correct
3 Incorrect 2 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 360 KB Output is correct
3 Incorrect 2 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -