Submission #165698

#	Time	Username	Problem	Language	Result	Execution time	Memory
165698		Hideo	Bosses (BOI16_bosses)	C++11	100 / 100	737 ms	764 KiB

bosses

// Need to git gud and reach 1900+
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>
using namespace std;

#define all(s) s.begin(), s.end()
#define ok puts("ok")
#define ll long long
#define pb push_back
#define mk make_pair
#define fr first
#define sc second
#define vi vector < int >
#define pi pair < int, int >
#define prev prev123
#define next next123
#define pow pow123
#define left left123
#define right right123

const int N = 5007;
const int INF = 1e9 + 7;

int us[N];
int n, ans = INF;

vi g[N];

int bfs (int s){
    memset(us, 0, sizeof(us));
    queue < pi > q;
    q.push(mk(s, 1));
    int res = 0;
    while (!q.empty()){
        int v = q.front().fr, h = q.front().sc;
        q.pop();
        if (us[v])
            continue;
        us[v] = 1;
        res += h;
        for (int to : g[v])
            if (!us[to])
                q.push(mk(to, h + 1));
    }
    for (int i = 1; i <= n; i++){
        if (!us[i])
            res = INF;
    }
    return res;
}

main(){ // If you don't know what to do, check the text box at the bottom
    cin >> n;
    for (int i = 1; i <= n; i++){
        int k;
        scanf("%d", &k);
        for (int j = 1; j <= k; j++){
            int a;
            scanf("%d", &a);
            g[a].pb(i);
        }
    }
    for (int i = 1; i <= n; i++)
        ans = min(ans, bfs(i));
    printf("%d", ans);
}

/*
    Totally not inspired by BenQ's template
    Things you should do:
    1. Look for stupid typos in code e.g 1 instead of -1 etc
    2. Check if there is no infinite loops
    3. "Measure twice, cut once"
    4. Stay focused
*/

Compilation message (stderr)

bosses.cpp:54:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){ // If you don't know what to do, check the text box at the bottom
      ^
bosses.cpp: In function 'int main()':
bosses.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &k);
         ~~~~~^~~~~~~~~~
bosses.cpp:61:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &a);
             ~~~~~^~~~~~~~~~

• Subtask 1: 22 / 22
• Subtask 2: 45 / 45
• Subtask 3: 33 / 33