oj.uz

Submission #458053

# Submission time Handle Problem Language Result Execution time Memory
458053 2021-08-07T22:43:28 Z ZaZo_ Bosses (BOI16_bosses) C++14
100 / 100
 826 ms 680 KB 
//Sorry but iam targeting IOI :))
//NEVER LOSE HOPE
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
#define endl "\n"
#define ceil(a,b)   (a+(b-1))/b
#define all(v) v.begin(),v.end()
#define int long long int
#define Hidden ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
const int N=3e4+10,mod = 1e9+7;
vector<int>edges[5001];
int mn=INT_MAX,val=0,n,ans=INT_MAX;
void bfs(int node)
{
  queue<pair<int,int>>q;
  q.push({node,1});
  int vis[5001]={0};
  vis[node]=1;
  int c=1;
  val=1;
  while(!q.empty())
  {
    int x=q.front().first , y=q.front().second;
    q.pop();
    for(auto i : edges[x])
    {
      if(!vis[i])
        vis[i]=1,q.push({i,y+1}),c++,val+=y+1;
    }
    //cout<<endl;
    if(c==n) break;
  }
  if(c==n) mn=min(mn,val);
}
int32_t main(){
  cin>>n;
  for(int i = 1 ; i <= n ; i ++)
  {
    int k;
    cin>>k;
    while(k--)
    {
      int x;
      cin>>x;
      edges[x].push_back(i);
    //  edges[x].push_back(i);
    }
  }
  for(int i = 1 ; i <= n ; i++)
  {
    bfs(i);
    ans=min(mn,ans);
    mn=INT_MAX;
  }
  cout<<ans<<endl;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 416 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 412 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 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 416 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 412 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 4 ms 552 KB Output is correct
13 Correct 4 ms 588 KB Output is correct
14 Correct 166 ms 564 KB Output is correct
15 Correct 13 ms 588 KB Output is correct
16 Correct 637 ms 680 KB Output is correct
17 Correct 826 ms 656 KB Output is correct
18 Correct 811 ms 648 KB Output is correct