oj.uz

답안 #994140

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
994140 2024-06-07T07:23:17 Z Sharky Bosses (BOI16_bosses) C++17
0 / 100
 0 ms 600 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 5001;
vector<int> adj[N];
int sz[N], ans = 0, opt = 1e9;
bool vis[N];

void dfs(int u) {
    vis[u] = true;
    sz[u] = 1;
    for (auto& v : adj[u]) {
        if (!vis[v]) {
            dfs(v);
            sz[u] += sz[v];
        }
    }
    ans += sz[u];
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n;
    cin >> n;
    for (int i = 1, j, x; i <= n; i++) {
        cin >> j;
        while (j--) {
            cin >> x;
            adj[x].push_back(i);
        }
    }
    for (int rt = 1; rt <= n; rt++) {
        ans = 0;
        for (int j = 1; j <= n; j++) vis[j] = 0, sz[j] = 0;
        dfs(rt);
        opt = min(opt, ans);
    }
    cout << opt << '\n';
}


//     1
//    2 3
//  456  78

//      8
//   4     3
// 1 1 1  1 1

// find sigma(sz[u])

Subtask #1
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 600 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 600 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 600 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -