oj.uz

Submission #337861

# Submission time Handle Problem Language Result Execution time Memory
337861 2020-12-22T03:48:32 Z KazamaHoang Bosses (BOI16_bosses) C++14
100 / 100
 1413 ms 1132 KB 
/* -> Written by <-
   -----------
  K_A_Z_A_M_A
  ___________
      _    |
  |   (^_^)   |
  |  /( | )\  |
  |____|_|____|
    H O A N G
*/

#include <bits/stdc++.h>

#define Task            ""
#define F               first
#define S               second
#define pb              push_back
#define bit(x, i)       ((x >> (i)) & 1)
#define inf             1e9 + 7
#define INF             1e18 + 7
#define ll              long long
#define pii             pair <int, int>
#define debug(x)        cerr << #x << " is " << x << "\n";

using namespace std;

const int MOD = 1e9 + 7;
const int maxn = 5005;

int n;
vector <int> ke[maxn], e[maxn];
bool dd[maxn];
int q[maxn];
int d[maxn];

void bfs(int u){
    int l = 0, r = 1;
    q[1] = u;
    dd[u] = -1;
    while (l < r){
        u = q[++l];
        for (auto v : ke[u])
            if (dd[v] == 0){
                dd[v] = 1;
                e[u].pb(v);
                q[++r] = v;
            }
    }
}

void dfs(int u){
    d[u] = 1;
    for (auto v : e[u]){
        dfs(v);
        d[u] += d[v];
    }
}

int OK(){
    int s = 0;
    for (int i = 1; i <= n; ++ i)
        if (d[i] == inf) return 0;
        else s += d[i];
    return s;
}

void Solve(){
    cin >> n;
    for (int i = 1; i <= n; ++ i){
        int x; cin >> x;
        for (int j = 1; j <= x; ++ j){
            int y; cin >> y;
            ke[y].pb(i);
        }
    }
    int res = inf;
    for (int i = 1; i <= n; ++ i){
        memset(dd, 0, sizeof(dd));
        for (int j = 1; j <= n; ++ j) e[j].clear();
        fill(d + 1, d + 1 + n, inf);
        bfs(i);
        dfs(i);
        int s = OK();
        if (s == 0) continue;
        res = min(res, s);
    }
    cout << res << "\n";
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    if(fopen(Task".inp", "r")){
        freopen(Task".inp","r",stdin);
        freopen(Task".out","w",stdout);
    }
    int test_case = 1;
    // cin >> test_case;
    while (test_case --){
        Solve();
    }

    return 0;
}

Compilation message

bosses.cpp: In function 'int main()':
bosses.cpp:93:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   93 |         freopen(Task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
bosses.cpp:94:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   94 |         freopen(Task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 1 ms 620 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 1 ms 620 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 1 ms 620 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 1 ms 620 KB Output is correct
7 Correct 1 ms 620 KB Output is correct
8 Correct 1 ms 620 KB Output is correct
9 Correct 1 ms 620 KB Output is correct
10 Correct 1 ms 620 KB Output is correct
11 Correct 1 ms 620 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 1 ms 620 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 1 ms 620 KB Output is correct
7 Correct 1 ms 620 KB Output is correct
8 Correct 1 ms 620 KB Output is correct
9 Correct 1 ms 620 KB Output is correct
10 Correct 1 ms 620 KB Output is correct
11 Correct 1 ms 620 KB Output is correct
12 Correct 5 ms 748 KB Output is correct
13 Correct 4 ms 764 KB Output is correct
14 Correct 327 ms 1004 KB Output is correct
15 Correct 43 ms 876 KB Output is correct
16 Correct 1089 ms 1004 KB Output is correct
17 Correct 1407 ms 1132 KB Output is correct
18 Correct 1413 ms 1132 KB Output is correct