oj.uz

Submission #556177

# Submission time Handle Problem Language Result Execution time Memory
556177 2022-05-02T14:45:31 Z Olympia Bosses (BOI16_bosses) C++17
0 / 100
 0 ms 212 KB 
#include <bits/stdc++.h>
using namespace std;
void dfs (vector<vector<int> > &adj, vector<int>& val, int curNode, int prevNode) {
    //cout << curNode << " " << prevNode << '\n';
    val[curNode] = 1;
    for (int i: adj[curNode]) {
        if (i != prevNode) {
            dfs (adj, val, i, curNode);
            val[curNode] += val[i];
        }
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    vector<vector<int> > adj;
    adj.resize(n);
    for (int i = 0; i < n; i++) {
        int k;
        cin >> k;
        while (k--) {
            int a;
            cin >> a;
            a--;
            adj[a].push_back(i);
        }
    }
    int myMin = INT_MAX;
    for (int i = 0; i < n; i++) {
        queue<int> q;
        q.push(i);
        vector<bool> hasVisited; hasVisited.assign(n, false);
        vector<vector<int> > new_adj(n);
        hasVisited[i] = true;
        while (!q.empty()) {
            int curNode = q.front();
            q.pop();
            for (int j: adj[curNode]) {
                if (!hasVisited[j]) {
                    q.push(j);
                    hasVisited[j] = true;
                    new_adj[j].push_back(curNode), new_adj[curNode].push_back(j);
                }
            }
        }
        bool fine = true;
        for (bool j: hasVisited) {
            if (!j) {
                fine = false;
            }
        }
        if (!fine) {
            continue;
        }
        vector<int> val(n);
        dfs(new_adj, val, i, i);
        int ans = 0;
        for (int j: val) {
            ans += j;
        }
        myMin = min(myMin, ans);
    }
}

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -