oj.uz

Submission #36402

# Submission time Handle Problem Language Result Execution time Memory
36402 2017-12-08T16:30:58 Z DoanPhuDuc Bosses (BOI16_bosses) C++
0 / 100
 0 ms 2308 KB 
#include <bits/stdc++.h>

#define FOR(x, a, b) for (int x = a; x <= b; ++x)
#define FOD(x, a, b) for (int x = a; x >= b; --x)
#define REP(x, a, b) for (int x = a; x < b; ++x)
#define DEBUG(X) { cout << #X << " = " << X << endl; }
#define PR(A, n) { cout << #A << " = "; FOR(_, 1, n) cout << A[_] << " "; cout << endl; }
#define PR0(A, n)  { cout << #A << " = "; REP(_, 0, n) cout << A[_] << " "; cout << endl; }

using namespace std;

typedef long long LL;
typedef pair <int, int> II;

const int N = 5e3 + 10;
const int INF = 0x3f3f3f3f;

int n, top = 0;
int f[N], p[N], st[N];

vector <int> boss[N], adj[N];

void DFS(int u) {
    f[u] = 1;
    REP(k, 0, adj[u].size()) {
        int v = adj[u][k];
        DFS(v);
        f[u] += f[v];
    }
}

int Compute(int u) {
    FOR(i, 1, n) {
        adj[i].clear();
        p[i] = -1;
    }
    p[u] = 0;
    top = 0;
    st[++top] = u;
    while (top > 0) {
        int u = st[top--];
        REP(k, 0, boss[u].size()) {
            int v = boss[u][k];
            if (p[v] == -1) {
                adj[u].push_back(v);
                p[v] = u;
                st[++top] = v;
            }
        }
    }
    int num = 0;
    FOR(i, 1, n) num += (p[i] != -1);
    if (num == n) {
        DFS(u);
        int ans = 0;
        FOR(i, 1, n) ans += f[i];
        return ans;
    } else return INF;
}

int main() {
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif // LOCAL
    scanf("%d", &n);
    FOR(i, 1, n) {
        int m; scanf("%d", &m);
        FOR(j, 1, m) {
            int x; scanf("%d", &x);
            boss[x].push_back(i);
        }
    }
    int ans = INF;
    FOR(i, 1, n) ans = min(ans, Compute(i));
    printf("%d\n", ans);
    return 0;
}

Compilation message

bosses.cpp: In function 'void DFS(int)':
bosses.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(x, a, b) for (int x = a; x < b; ++x)
                                        ^
bosses.cpp:25:5: note: in expansion of macro 'REP'
     REP(k, 0, adj[u].size()) {
     ^
bosses.cpp: In function 'int Compute(int)':
bosses.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(x, a, b) for (int x = a; x < b; ++x)
                                        ^
bosses.cpp:42:9: note: in expansion of macro 'REP'
         REP(k, 0, boss[u].size()) {
         ^
bosses.cpp: In function 'int main()':
bosses.cpp:66:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
bosses.cpp:68:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int m; scanf("%d", &m);
                               ^
bosses.cpp:70:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             int x; scanf("%d", &x);
                                   ^

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2308 KB Output is correct
2 Correct 0 ms 2308 KB Output is correct
3 Incorrect 0 ms 2308 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2308 KB Output is correct
2 Correct 0 ms 2308 KB Output is correct
3 Incorrect 0 ms 2308 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2308 KB Output is correct
2 Correct 0 ms 2308 KB Output is correct
3 Incorrect 0 ms 2308 KB Output isn't correct
4 Halted 0 ms 0 KB -