oj.uz

Submission #408822

# Submission time Handle Problem Language Result Execution time Memory
408822 2021-05-19T17:15:36 Z danielcm585 Bosses (BOI16_bosses) C++14
0 / 100
 1 ms 460 KB 
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second

typedef long long ll;
typedef pair<int,int> ii;

const int N = 5e3;
const ll INF = 1e15;
int n;
bool use[N+2];
ll val[N+2];
vector<int> lst[N+2], adj[N+2];

ll dfs(int cur, int par) {
    if (!use[cur]) return INF;
    ll ret = 0;
    val[cur] = 0;
    for (int nx : adj[cur]) {
        if (nx == par) continue;
        ret += dfs(nx,cur);
        val[cur] += val[nx];
    }
    val[cur]++;
    ret += val[cur];
    return ret;
}

ll bfs(int st) {
    for (int i = 1; i <= n; i++) adj[i].clear();
    memset(use,0,sizeof(use));
    queue<int> q;
    q.push(st); use[st] = 1;
    while (!q.empty()) {
        int cur = q.front(); q.pop();
        for (int nx : lst[cur]) {
            if (use[nx]) continue;
            use[nx] = 1;
            adj[cur].push_back(nx);
            q.push(nx);
        }
    }
    // cout << st << " -> " << dfs(st,0) << '\n';
    // cout << ">> ";
    // for (int j = 1; j <= n; j++) cout << val[j] << ' ';
    // cout << '\n';
    return dfs(st,0);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int k; cin >> k;
        for (int j = 1; j <= k; j++) {
            int x; cin >> x;
            lst[x].push_back(i);
        }
    }
    ll ans = INF;
    for (int i = 1; i <= n; i++) {
        ans = min(ans,bfs(i));
    }
    cout << ans << '\n';
    return 0;
}

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Incorrect 1 ms 460 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 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Incorrect 1 ms 460 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 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Incorrect 1 ms 460 KB Output isn't correct
4 Halted 0 ms 0 KB -