oj.uz

Submission #107395

# Submission time Handle Problem Language Result Execution time Memory
107395 2019-04-23T20:16:59 Z aryaman Bosses (BOI16_bosses) C++14
100 / 100
 702 ms 696 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;

typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ld> vd;
typedef vector<ll> vl;

typedef set<int> si;
typedef set<ii> sii;
typedef set<ld> sd;
typedef set<ll> sl;

typedef map<int, int> mii;
typedef priority_queue<int> pqi;
typedef queue<int> qi;
 
#define mp make_pair
#define pb push_back
#define f first
#define s second

mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());

const ll INF = numeric_limits<ll>::max();

ll bfs(int s, vector<vi> &g) {
    vector<bool> vis(g.size());
    queue<ii> bfs;
    bfs.push({s, 0});
    ll res = 0;
    int visited = 0;
    while (!bfs.empty()) {
        ii u = bfs.front();
        bfs.pop();
        res += u.s + 1;
        vis[u.f] = true;
        visited++;
        for (auto &v : g[u.f]) {
            if (vis[v]) continue;
            bfs.push({v, u.s + 1});
            vis[v] = true;
        }
    }
    return (visited == g.size() ? res : INF);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<vi> g(n);
    for (int i = 0; i < n; i++) {
        int m; cin >> m;
        while (m--) {
            int j; cin >> j, j--;
            g[j].push_back(i);
        }
    }

    ll ans = numeric_limits<ll>::max();
    for (int i = 0; i < n; i++) {
        ans = min(ans, bfs(i, g));
    }

    cout << ans << endl;
}

/*
USE LONG LONG!!!!

1 1 2 4
1 2 2 3
2 2 2 2

:pray: :fishy15:
:pray: :summitosity:
:pray: :prodakcin:

          .=     ,        =.
  _  _   /'/    )\,/,/(_   \ \
   `//-.|  (  ,\\)\//\)\/_  ) |
   //___\   `\\\/\\/\/\\///'  /
,-"~`-._ `"--'_   `"""`  _ \`'"~-,_
\       `-.  '_`.      .'_` \ ,-"~`/
 `.__.-'`/   (-\        /-) |-.__,'
   ||   |     \O)  /^\ (O/  | .        <-  BESSIE THE COW
   `\\  |         /   `\    /
     \\  \       /      `\ /
      `\\ `-.  /' .---.--.\
        `\\/`~(, '()      ('
         /(O) \\   _,.-.,_)    
        //  \\ `\'`      /
       / |  ||   `""""~"`
     /'  |__||
           `o
*/

Compilation message

bosses.cpp: In function 'll bfs(int, std::vector<std::vector<int> >&)':
bosses.cpp:53:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     return (visited == g.size() ? res : INF);
             ~~~~~~~~^~~~~~~~~~~

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 8 ms 512 KB Output is correct
13 Correct 6 ms 492 KB Output is correct
14 Correct 156 ms 632 KB Output is correct
15 Correct 5 ms 512 KB Output is correct
16 Correct 593 ms 544 KB Output is correct
17 Correct 651 ms 640 KB Output is correct
18 Correct 702 ms 696 KB Output is correct