oj.uz

Submission #513778

# Submission time Handle Problem Language Result Execution time Memory
513778 2022-01-17T15:39:16 Z joshualiu555 Bosses (BOI16_bosses) C++17
100 / 100
 1376 ms 936 KB 
/*
  _____                                     _        _
 / ____|                                   | |      | |
| |  __ _ __ __ _ ___ ___ _   _ _ __   ___ | |_ __ _| |_ ___
| | |_ | '__/ _` / __/ __| | | | '_ \ / _ \| __/ _` | __/ _ \
| |__| | | | (_| \__ \__ \ |_| | |_) | (_) | || (_| | || (_) |
 \_____|_|  \__,_|___/___/\__, | .__/ \___/ \__\__,_|\__\___/
                           __/ | |
                          |___/|_|
*/

#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

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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 532 KB Output is correct
4 Correct 1 ms 560 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 0 ms 460 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 532 KB Output is correct
4 Correct 1 ms 560 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 0 ms 460 KB Output is correct
7 Correct 1 ms 552 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 556 KB Output is correct
11 Correct 1 ms 460 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 532 KB Output is correct
4 Correct 1 ms 560 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 0 ms 460 KB Output is correct
7 Correct 1 ms 552 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 556 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 5 ms 692 KB Output is correct
13 Correct 4 ms 716 KB Output is correct
14 Correct 222 ms 856 KB Output is correct
15 Correct 21 ms 756 KB Output is correct
16 Correct 683 ms 892 KB Output is correct
17 Correct 1376 ms 932 KB Output is correct
18 Correct 1362 ms 936 KB Output is correct