oj.uz

Submission #582702

# Submission time Handle Problem Language Result Execution time Memory
582702 2022-06-24T09:48:35 Z Omar_Elgedawy Bosses (BOI16_bosses) C++14
100 / 100
 722 ms 640 KB 
#include <bits/stdc++.h>
using namespace std;
#define cin(vec)        for(auto& i : vec) cin >> i
#define cout(vec)       for(auto& i : vec) cout << i << " "; cout << "\n";
#define fast            ios::sync_with_stdio(0);cin.tie(0);
#define loop(i,a,b)     for (int i = a; i < b; i++)
#define F               first
#define S               second
#define pb(n)           push_back(n)
#define pf(n)           push_front(n)
#define dci(d)          fixed<<setprecision(d)
#define sp              ' '
#define el              '\n'
#define all(v)          v.begin(),v.end()
#define int             long long
int dx[8]= {0,0,1,-1,-1,1,1,-1};
int dy[8]= {-1,1,0,0,-1,1,-1,1};
int const N=5e3+1,M=1e3+1,Mod=1e9+7;
vector<int>adj[N];
int cnt=0,sum=0;
int vis[N];
void bfs(int st){
  queue<pair<int,int>>q;
  q.push({st,1});
  vis[st]=1;
  cnt++;
  while(q.size()){
    pair<int,int>u=q.front();
    q.pop();
    sum+=u.S;
    for(auto v:adj[u.F]){
      if(!vis[v]){
        vis[v]=1;
        cnt++;
        q.push({v,u.S+1});
      }
    }
  }
}
void testcase(int h){
  int n;cin>>n;
  for(int i=1;i<=n;i++){
    int k ;cin>>k;
    while(k--){
      int v;cin>>v;
      adj[v].push_back(i);
    }
  }
  int ans=1e18;
  for(int i=1;i<=n;i++){
    memset(vis,0,sizeof vis);
    cnt=0,sum=0;
    bfs(i);
    if(cnt!=n)continue;
    ans=min(ans,sum);
  }
  cout<<ans<<el;
}
int32_t main()
{
  fast
  testcase(1);
  // int tc;cin>>tc;for(int i=1;i<=tc;i++)testcase(i);
  return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 5 ms 596 KB Output is correct
13 Correct 4 ms 596 KB Output is correct
14 Correct 179 ms 560 KB Output is correct
15 Correct 8 ms 468 KB Output is correct
16 Correct 564 ms 640 KB Output is correct
17 Correct 719 ms 628 KB Output is correct
18 Correct 722 ms 624 KB Output is correct