oj.uz

Submission #522742

# Submission time Handle Problem Language Result Execution time Memory
522742 2022-02-05T15:12:18 Z nikolapesic2802 Bosses (BOI16_bosses) C++14
100 / 100
 1196 ms 1192 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);
      bool ok=1;
      for(int i=1;i<=n;i++)
        if(!pos[i])
          ok=0;
      if(ok)
        mini=min(mini, uk);
    }
    cout << mini;
    return 0;
}

Subtask #1
22.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 Correct 1 ms 460 KB Output is correct
4 Correct 0 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct

Subtask #2
45.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 Correct 1 ms 460 KB Output is correct
4 Correct 0 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 556 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 460 KB Output is correct

Subtask #3
33.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 Correct 1 ms 460 KB Output is correct
4 Correct 0 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 556 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 4 ms 716 KB Output is correct
13 Correct 3 ms 844 KB Output is correct
14 Correct 294 ms 816 KB Output is correct
15 Correct 41 ms 764 KB Output is correct
16 Correct 946 ms 1192 KB Output is correct
17 Correct 1196 ms 964 KB Output is correct
18 Correct 1161 ms 920 KB Output is correct