oj.uz

Submission #159552

# Submission time Handle Problem Language Result Execution time Memory
159552 2019-10-23T08:07:47 Z InfiniteJest Bosses (BOI16_bosses) C++14
100 / 100
 1161 ms 952 KB 
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <math.h>
#include <map>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
 
ifstream in("input.txt");
ofstream out("output.txt");
 
typedef long long ll;
 
int fi(){
  char g=getchar_unlocked();
  while(g<'0'||g>'9')g=getchar_unlocked();
  int num=0;
  while(g>='0'&&g<='9'){
    num=(num<<1)+(num<<3)+g-48;
    g=getchar_unlocked();
  }
  return num;
}
 
int n;
vector<int> nodi[5001];
vector<int> p[5001];
bool vis[5001];
int minn=1e9;
int val[5001];
int f;
int sum=0;
 
void bfs(int k){
  queue<pair<int,int> > q;
  q.push(mp(k,1));
  vis[k]=1;
  while(!q.empty()){
    int cur=q.front().fi;
    f++;
    int depth=q.front().se;
    sum+=q.front().se;
    q.pop();
    for(int i=0;i<nodi[cur].size();i++){
      if(vis[nodi[cur][i]])continue;
      vis[nodi[cur][i]]=1;
      q.push(mp(nodi[cur][i],depth+1));
    }
  }
}
 
 
int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  n=fi();
  for(int i=0;i<n;i++){
    int k; k=fi();
    for(int y=0;y<k;y++){
      int a; a=fi();
      nodi[a-1].pb(i);
    }
  }
  for(int i=0;i<n;i++){
    for(int y=0;y<n;y++){
      p[y].clear();
      vis[y]=0;
      val[y]=0;
    }
    f=0;
    sum=0;
    bfs(i);
    if(f!=n)continue;
    minn=min(minn,sum);
    //cout<<"i "<<i<<" v "<<sum<<endl;
  }
  cout<<minn;
}

Compilation message

bosses.cpp: In function 'void bfs(int)':
bosses.cpp:49:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<nodi[cur].size();i++){
                 ~^~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 2 ms 632 KB Output is correct
3 Correct 2 ms 632 KB Output is correct
4 Correct 2 ms 632 KB Output is correct
5 Correct 2 ms 632 KB Output is correct
6 Correct 2 ms 632 KB Output is correct
7 Correct 2 ms 632 KB Output is correct
8 Correct 2 ms 632 KB Output is correct
9 Correct 2 ms 632 KB Output is correct
10 Correct 2 ms 632 KB Output is correct
11 Correct 3 ms 636 KB Output is correct
12 Correct 7 ms 764 KB Output is correct
13 Correct 6 ms 760 KB Output is correct
14 Correct 272 ms 848 KB Output is correct
15 Correct 59 ms 632 KB Output is correct
16 Correct 864 ms 844 KB Output is correct
17 Correct 1161 ms 932 KB Output is correct
18 Correct 1145 ms 952 KB Output is correct