oj.uz

Submission #210178

# Submission time Handle Problem Language Result Execution time Memory
210178 2020-03-16T18:46:15 Z bash Bosses (BOI16_bosses) C++17
100 / 100
 1326 ms 916 KB 
/**
    SXR0aXAkI0JwbXptI3FhI3Z3I293bCNqY2IjUG0jMCNicG0jVHFkcXZvLyNCcG0jQW10bjBhY2phcWFicXZvLyNNYm16dml0MSNWdyNhdGN1am16I2tpdiNhbXF9bSNQcXUjVnd6I0F0bW14MSNQcWEjaXptI2l0dCNicHF2b2EjUXYjYnBtI3BtaWRtdmEjaXZsI3d2I21pemJwMSNFcHcjcWEjYnBtem0ja2l2I3F2Ym16a21sbSNRdiNQcWEjeHptYW12a20jbXtrbXhiI0lhI3BtI3htenVxYmJtYnBHI1BtI3N2d2VtYnAjRXBpYiMraXh4bWl6bWJwI2J3I1BxYSNrem1pYmN6bWEjSWEsI0ptbnd6bSN3eiNJbmJteiN3eiNKbXBxdmwjYnBtdTEjVnd6I2FwaXR0I2JwbXwja3d1eGlhYSNJY29wYiN3biNwcWEjc3Z3ZXRtbG9tI017a214YiNpYSNQbSNlcXR0bWJwMSNQcWEjYnB6d3ZtI2x3YnAjbXtibXZsI1dkbXojYnBtI3BtaWRtdmEjSXZsI3d2I21pemJwLyNpdmwjUG0jbm1tdG1icCNWdyNuaWJxb2NtI3F2I29jaXpscXZvI0l2bCN4em1hbXpkcXZvI2JwbXUvI053eiNQbSNxYSNicG0jVXdhYiNQcW9wMSNCcG0jQWN4em11bSMrcXYjb3R3enwsMQ==
    */
#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>

#define F first
#define S second
#define endl '\n'
#define deb(x) cout<<#x<<' '<<x<<endl;
#define pb push_back


#ifdef IZI_KATKA
#define int __int64_t
#else
#define int __int64_t
#endif

const long long MOD = 1e18 + 7;
const long long MAXN = 5001 + 1;
using namespace std;

typedef long long ll;

long long readInt() {
  bool minus1 = false;
  long long result = 0;
  char ch;
  ch = getchar();
  while (true) {
    if (ch == '-') break;
    if (ch >= '0' && ch <= '9') break;
    ch = getchar();
  }
  if (ch == '-') minus1 = true; else result = ch-'0';
  while (true) {
    ch = getchar();
    if (ch < '0' || ch > '9') break;
    result = result*10 + (ch - '0');
  }
  if (minus1)
    return -result;
  else
    return result;
}

int ans[MAXN];
int used[MAXN];
vector <int> g[MAXN];
int par[MAXN];
int n;
vector<int> vec;


int bfs(int s) {
  memset(used, 0, sizeof(used));
  memset(ans, 0, sizeof(ans));
  queue<int> q;
  vec.clear();
  q.push (s);
  used[s] = true;
  par[s] = -1;
  while (!q.empty()) {
    int v = q.front();
    q.pop();
    vec.push_back(v);
    for (size_t i=0; i<g[v].size(); ++i) {
      int to = g[v][i];
      if (!used[to]) {
        used[to] = true;
        q.push (to);

        par[to] = v;
      }
    }
  }
  if(vec.size() != n) return MOD;
  int tot = 0;
  for (int i = vec.size() - 1; i >= 0; i--) {
    ans[vec[i]]++;
    tot += ans[vec[i]];
    if (par[vec[i]] != -1) {
      ans[par[vec[i]]] += ans[vec[i]];
    }
  }	
  return tot;
}

main() {
  #ifdef IZI_KATKA
  assert(freopen("input", "r", stdin));
  assert(freopen("output", "w", stdout));
  #endif
  n = readInt();
  for (int i = 1; i <= n; i++) {
    int m = readInt();
    for (int j = 1; j <= m; j++) {
      int x = readInt();
      g[x].pb(i);
    }
  }
  int res = MOD;
  for (int i = 1; i <= n; i++) {
    res = min(res, bfs(i));    	
  }
  cout << res;
  return 0;
}

Compilation message

bosses.cpp: In function '__int64_t bfs(__int64_t)':
bosses.cpp:97:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(vec.size() != n) return MOD;
      ~~~~~~~~~~~^~~~
bosses.cpp: At global scope:
bosses.cpp:109:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 5 ms 504 KB Output is correct
5 Correct 5 ms 504 KB Output is correct
6 Correct 5 ms 504 KB Output is correct
7 Correct 5 ms 504 KB Output is correct
8 Correct 5 ms 504 KB Output is correct
9 Correct 6 ms 504 KB Output is correct
10 Correct 5 ms 504 KB Output is correct
11 Correct 5 ms 504 KB Output is correct
12 Correct 10 ms 632 KB Output is correct
13 Correct 9 ms 632 KB Output is correct
14 Correct 221 ms 760 KB Output is correct
15 Correct 20 ms 760 KB Output is correct
16 Correct 834 ms 888 KB Output is correct
17 Correct 1326 ms 916 KB Output is correct
18 Correct 1294 ms 892 KB Output is correct