oj.uz

Submission #510055

# Submission time Handle Problem Language Result Execution time Memory
510055 2022-01-14T15:46:32 Z Habitus Bosses (BOI16_bosses) C++14
0 / 100
 1 ms 560 KB 
#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
ll n, mini;
vector<ll> graf[5010], detsa[5010];
bool pos[5010];
ll uk;
void bfs(ll poc) {
    queue<ll> q;
    pos[poc]=true;
    q.emplace(poc);
    while(!q.empty()) {
        ll tren=q.front(); q.pop();
        for(auto adj:graf[tren]) {
            if(pos[adj]) continue;
            pos[adj]=true;
            q.emplace(adj);
            detsa[tren].push_back(adj);
        }
    }
}
ll racunaj(ll node) {
    ll suma=1LL;
    for(auto dete:detsa[node]) {
        suma+=racunaj(dete);
    }
    uk+=suma;
    return suma;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    mini=2000000000000000LL;
    cin >> n;
    for(ll i=1; i<=n; ++i) {
        ll k; cin >> k;
        while(k--) {
            ll x; cin >> x;
            graf[x].push_back(i);
        }
    }
    for(ll root=1; root<=n; ++root) {
        for(ll i=1; i<=n; ++i) pos[i]=false;
        for(ll i=1; i<=n; ++i) detsa[i].clear();
 
        uk=0LL;
        bfs(root);
        racunaj(root);
        mini=min(mini, uk);
    }
    cout << mini;
    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 560 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 560 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 560 KB Output isn't correct
4 Halted 0 ms 0 KB -