Submission #513778

#	Time	Username	Problem	Language	Result	Execution time	Memory
513778		joshualiu555	Bosses (BOI16_bosses)	C++17	100 / 100	1376 ms	936 KiB

bosses

/*
  _____                                     _        _
 / ____|                                   | |      | |
| |  __ _ __ __ _ ___ ___ _   _ _ __   ___ | |_ __ _| |_ ___
| | |_ | '__/ _` / __/ __| | | | '_ \ / _ \| __/ _` | __/ _ \
| |__| | | | (_| \__ \__ \ |_| | |_) | (_) | || (_| | || (_) |
 \_____|_|  \__,_|___/___/\__, | .__/ \___/ \__\__,_|\__\___/
                           __/ | |
                          |___/|_|
*/

#pragma gcc target ("avx2")
#pragma gcc optimization ("O3")
#pragma gcc optimization ("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template<class T> using segset = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, x, n) for (int i = x; i <= n; i++)
#define F0R(i, x, n) for (int i = x; i >= n; i--)
#define TRAV(it, x) for (auto it = x.begin(); it != x.end(); it++)
#define rall(x) x.rbegin(), x.rend()
#define all(x) x.begin(), x.end()
//#define f first
//#define s second
#define sz size
#define pob pop_back
#define pb push_back
#define ins insert
#define mp make_pair
#define rz resize
#define rev reverse
#define lb lower_bound
#define ub upper_bound
// fill for 1
// 0x3f3f3f3f for 1e9
#define mem(a, x) memset(a, x, sizeof(a))
#define HEX 0x3f3f3f3f

using ll = long long;
const int INF = 5005;
const int MOD = 1e9 + 7;
// DLRU
const int dx[4] = {1, 0, 0, -1};
const int dy[4] = {0, -1, 1, 0};

int n;
vector<int> adj[INF];

vector<int> adj2[INF];
bool visited[INF];

int salary = 0;
bool visited2[INF];
int dfs(int node) {
    int cnt = 1;
    visited2[node] = true;
    for (auto neighbor : adj2[node]) {
        if (!visited2[neighbor]) {
            cnt += dfs(neighbor);
        }
    }
    salary += cnt;
    return cnt;
}

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

    cin >> n;
    FOR(i, 1, n) {
        int k;
        cin >> k;
        while (k--) {
            int x;
            cin >> x;
            adj[x].pb(i);
        }
    }

    int ans = 1e9;
    FOR(i, 1, n) {
        FOR(j, 1, n) adj2[j].clear();
        mem(visited, false);
        queue<int> q;
        q.push(i);
        visited[i] = true;
        int num_visited = 0;
        while (!q.empty()) {
            int node = q.front();
            q.pop();
            num_visited++;
            for (auto neighbor : adj[node]) {
                if (!visited[neighbor]) {
                    adj2[node].pb(neighbor);
                    visited[neighbor] = true;
                    q.push(neighbor);
                }
            }
        }
        if (num_visited == n) {
            cerr << endl;
            mem(visited2, false);
            salary = 0;
            dfs(i);
            ans = min(ans, salary);
        }
    }

    cout << ans << '\n';

    return 0;
}

/*
 * for each node, draw a direct edge from its
 * accepted boss to the node
 *
 * fix each node as the root node
 * bfs the ideal tree
 * for each iteration, push the next visited
 * neighbors into an adj list for the current node
 *
 * if all nodes are visited, this tree is valid
 * use dfs and set each leaf to 1 and
 * work your way up to the level 99 mafia boss
*/

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

Compilation message (stderr)

bosses.cpp:12: warning: ignoring '#pragma gcc target' [-Wunknown-pragmas]
   12 | #pragma gcc target ("avx2")
      | 
bosses.cpp:13: warning: ignoring '#pragma gcc optimization' [-Wunknown-pragmas]
   13 | #pragma gcc optimization ("O3")
      | 
bosses.cpp:14: warning: ignoring '#pragma gcc optimization' [-Wunknown-pragmas]
   14 | #pragma gcc optimization ("unroll-loops")
      |

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