Submission #32714

#	Time	Username	Problem	Language	Result	Execution time	Memory
32714		jjwdi0	Bosses (BOI16_bosses)	C++11	67 / 100	1500 ms	2672 KiB

bosses

#include <bits/stdc++.h>
using namespace std;
 
int N, sz[5003];
vector<int> v[5003];
vector<int> tree[5003];
bool visited[5003];
queue<int> q;
 
void dfs(int x, int p) {
    for(int it : tree[x]) {
        if(it == p) continue;
        dfs(it, x);
        sz[x] += sz[it];
    }
    sz[x]++;
}
 
int score(int x) {
    dfs(x, 0);
    int res = 0;
    for(int i=1; i<=N; i++) {
        if(sz[i]) res += sz[i];
        else res = 1e9;
    }
    return res;
}
 
int main() {
    scanf("%d", &N);
    for(int i=1, x; i<=N; i++) {
        scanf("%d", &x);
        for(int j=0, y; j<x; j++) {
            scanf("%d", &y);
            v[y].push_back(i);
        }
    }
    int ans = 2e9;
    for(int i=1; i<=N; i++) {
        q.push(i);
        for(int j=1; j<=N; j++) visited[j] = 0, sz[j] = 0, tree[j].clear();
        visited[i] = 1;
        while(!q.empty()) {
            int u = q.front(); q.pop();
            for(int it : v[u]) {
                if(visited[it]) continue;
                tree[u].push_back(it);
                tree[it].push_back(u);
                visited[it] = 1;
                q.push(it);
            }
        }
        ans = min(ans, score(i));
    }
    printf("%d\n", ans);
}

Compilation message (stderr)

bosses.cpp: In function 'int main()':
bosses.cpp:30:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
                    ^
bosses.cpp:32:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &x);
                        ^
bosses.cpp:34:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &y);
                            ^

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