oj.uz

Submission #723603

# Submission time Handle Problem Language Result Execution time Memory
723603 2023-04-14T06:06:31 Z The_Samurai Hacker (BOI15_hac) C++17
0 / 100
 780 ms 262144 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2")

#include "bits/stdc++.h"

using namespace std;
using ll = long long;
int INF = 2e9;

vector<int> cost;
vector<vector<int>> g;

void dfs(int u) {
    for (int v: g[u]) {
        dfs(v);
        cost[u] += cost[v];
    }
}

void solve() {
    int n;
    cin >> n;
    vector<vector<int>> in(n + 1), out(n + 1);
    for (int i = 1; i <= n; i++) {
        int k;
        cin >> k;
        while (k--) {
            int j;
            cin >> j;
            in[j].emplace_back(i);
            out[i].emplace_back(j);
        }
    }
    int ans = 2e9;
    for (int i = 1; i <= n; i++) {
        // root -> i
        queue<int> qu;
        vector<bool> vis(n + 1);
        cost.assign(n + 1, 1);
        g.assign(n + 1, {});
        vis[i] = 1;
        for (int j: in[i]) {
            g[i].emplace_back(j);
            qu.push(j);
            vis[j] = 1;
        }
        while (!qu.empty()) {
            int u = qu.front();
            qu.pop();
            for (int v: in[u]) {
                if (!vis[v]) {
                    g[u].emplace_back(v);
                    qu.push(v);
                    vis[v] = 1;
                }
            }
        }
        bool ok = 1;
        for (int j = 1; j <= n; j++) {
            if (!vis[j]) ok = 0;
        }
        if (!ok) continue;
        dfs(i);
        int now = 0;
        for (int j = 1; j <= n; j++)
            now += cost[j];
        ans = min(ans, now);
    }
    cout << ans;
}

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

    int queries = 1;
#ifdef test_cases
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
//    cin >> queries;
#else
    //    cin >> queries;
#endif

    for (int test_case = 1; test_case <= queries; test_case++) {
        solve();
//        cout << '\n';
    }
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 742 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 742 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 780 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 742 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -