oj.uz

Submission #438177

# Submission time Handle Problem Language Result Execution time Memory
438177 2021-06-27T17:40:57 Z Urvuk3 Bosses (BOI16_bosses) C++17
0 / 100
 30 ms 32588 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long
const ll MAXN=1e6,INF=1e10 ;
#define fi first
#define se second
#define pll pair<ll,ll>
#define pii pair<int,int>
#define mid (l+r)/2
#define sz(a) int((a).size())
#define all(a) a.begin(),a.end()
#define mod 1000000007LL
#define endl "\n"
#define PRINT(x) cout<<#x<<'-'<<x<<endl

ll n, m, k, q, l, r, x, y, z, res=INF, tmp=0;
string s,t;
vector<int> adj[MAXN];
ll dist[MAXN];
bool visited[MAXN];

void bfs(int x){
    queue<int> q;
    dist[x]=1;
    visited[x]=true;
    q.push(x);
    while(!q.empty()){
        int s=q.front(); q.pop();
        for(auto v:adj[s]){
            if(visited[v]) continue;
            visited[v]=true;
            dist[v]=dist[s]+1;
            q.push(v);
        }
    }
}

void solve(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>q;
        for(int j=0;j<q;j++){
            cin>>x;
            adj[x].push_back(i);
        }
    }
    for(int i=1;i<=n;i++){
        memset(visited,false,sizeof(visited));
        memset(dist,0,sizeof(dist));
        tmp=0;
        bfs(i);
        for(int i=1;i<=n;i++){
            if(!visited[i]) continue;
        }
        for(int i=1;i<=n;i++){
            tmp+=dist[i];
        }
        res=min(res,tmp);
    }
    cout<<res<<endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int t;
    //cin>>t;
    t=1;
    while(t--){
        solve();
    }
    return 0;
}

Subtask #1
0 / 22.0

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

Subtask #2
0 / 45.0

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

Subtask #3
0 / 33.0

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