oj.uz

Submission #51281

# Submission time Handle Problem Language Result Execution time Memory
51281 2018-06-17T11:26:50 Z mareksom Bosses (BOI16_bosses) C++17
100 / 100
 702 ms 1488 KB 
#ifndef LOCAL
#pragma GCC optimize ("O3")
#endif

#include <bits/stdc++.h>

using namespace std;

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return {i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (c it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(x...) " [" #x ": " << (x) << "] "

using ld = long double;
using ll = long long;

constexpr int mod = 1000 * 1000 * 1000 + 7;
constexpr int odw2 = (mod + 1) / 2;

void OdejmijOd(int& a, int b) { a -= b; if (a < 0) a += mod; }
int Odejmij(int a, int b) { OdejmijOd(a, b); return a; }
void DodajDo(int& a, int b) { a += b; if (a >= mod) a -= mod; }
int Dodaj(int a, int b) { DodajDo(a, b); return a; }
int Mnoz(int a, int b) { return (ll) a * b % mod; }
void MnozDo(int& a, int b) { a = Mnoz(a, b); }
int Pot(int a, int b) { int res = 1; while (b) { if (b % 2 == 1) MnozDo(res, a); a = Mnoz(a, a); b /= 2; } return res; }
int Odw(int a) { return Pot(a, mod - 2); }
void PodzielDo(int& a, int b) { MnozDo(a, Odw(b)); }
int Podziel(int a, int b) { return Mnoz(a, Odw(b)); }
int Moduluj(ll x) { x %= mod; if (x < 0) x += mod; return x; }

template <typename T> T Maxi(T& a, T b) { return a = max(a, b); }
template <typename T> T Mini(T& a, T b) { return a = min(a, b); }

constexpr int nax = 5005;

int n;
vector<int> graf[nax];

int wynik = nax * nax;
int licz;
int czas = 100;

int odw[nax];
int gleb[nax];

void OgarnijZ(int w) {
  licz = 0;
  czas++;

  queue<int> kol;
  kol.push(w);
  gleb[w] = 1;
  odw[w] = czas;

  while (!kol.empty()) {
    w = kol.front();
    kol.pop();
    licz += gleb[w];
    for (int x : graf[w]) {
      if (odw[x] != czas) {
        odw[x] = czas;
        gleb[x] = gleb[w] + 1;
        kol.push(x);
      }
    }
  }

  for (int i = 1; i <= n; i++) {
    if (odw[i] != czas) {
      return;
    }
  }

  Mini(wynik, licz);
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    int k;
    cin >> k;
    while (k--) {
      int x;
      cin >> x;
      graf[x].push_back(i);
    }
  }

  for (int i = 1; i <= n; i++) {
    OgarnijZ(i);
  }

  cout << wynik << endl;
  return 0;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 548 KB Output is correct
4 Correct 2 ms 572 KB Output is correct
5 Correct 2 ms 572 KB Output is correct
6 Correct 2 ms 628 KB Output is correct
7 Correct 2 ms 632 KB Output is correct
8 Correct 2 ms 636 KB Output is correct
9 Correct 2 ms 672 KB Output is correct
10 Correct 2 ms 672 KB Output is correct
11 Correct 2 ms 784 KB Output is correct
12 Correct 7 ms 944 KB Output is correct
13 Correct 6 ms 944 KB Output is correct
14 Correct 118 ms 1040 KB Output is correct
15 Correct 5 ms 1044 KB Output is correct
16 Correct 599 ms 1212 KB Output is correct
17 Correct 667 ms 1300 KB Output is correct
18 Correct 702 ms 1488 KB Output is correct