oj.uz

Submission #824276

# Submission time Handle Problem Language Result Execution time Memory
824276 2023-08-13T23:01:29 Z AlphaMale06 Bosses (BOI16_bosses) C++14
100 / 100
 841 ms 900 KB 
#include <bits/stdc++.h>
#define pb push_back
using namespace std;

const int N=5005;
vector<int> adj[N];
vector<int> adj1[N];
bool mark[N];
int ans=0;
int cnt=0;

int dfs(int node, int p){
    int ret=1;
    for(auto to : adj1[node]){
        if(to!=p){
            ret+=dfs(to, node);
        }
    }
    ans+=ret;
    return ret;
}

void bfs(int node){
    mark[node]=true;
    cnt=1;
    int sum=1;
    queue<int> q;
    q.push(node);
    while(!q.empty()){
        int nd=q.front();
        for(auto to : adj[nd]){
            if(!mark[to]){
                q.push(to);
                mark[to]=true;
                adj1[nd].pb(to);
                cnt++;
            }
        }
        q.pop();
    }
    dfs(node, -1);
}


void clearmark(int n){
    for(int i=1; i<= n; i++){
        mark[i]=0;
        adj1[i].clear();
    }
}
int main()
{
    int n;
    cin >> n;
    for(int i=0; i< n; i++){
        int k;
        cin >> k;
        for(int j=0; j< k; j++){
            int kita;
            cin >> kita;
            adj[kita].pb(i+1);
        }
    }
    int mn=1e9;
    for(int i=1; i<=n; i++){
        bfs(i);
        if(cnt==n)mn=min(mn, ans);
        clearmark(n+1);
        ans=0;
    }
    cout << mn << '\n';
}

Compilation message

bosses.cpp: In function 'void bfs(int)':
bosses.cpp:26:9: warning: unused variable 'sum' [-Wunused-variable]
   26 |     int sum=1;
      |         ^~~

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 544 KB Output is correct
3 Correct 1 ms 544 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 544 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 540 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 6 ms 688 KB Output is correct
13 Correct 3 ms 620 KB Output is correct
14 Correct 206 ms 788 KB Output is correct
15 Correct 22 ms 688 KB Output is correct
16 Correct 751 ms 860 KB Output is correct
17 Correct 819 ms 900 KB Output is correct
18 Correct 841 ms 900 KB Output is correct