Submission #107395

#	Time	Username	Problem	Language	Result	Execution time	Memory
107395		aryaman	Bosses (BOI16_bosses)	C++14	100 / 100	702 ms	696 KiB

bosses

#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 (stderr)

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 / 22
• Subtask 2: 45 / 45
• Subtask 3: 33 / 33