Submission #654488

#	Time	Username	Problem	Language	Result	Execution time	Memory
654488		LCJLY	Bosses (BOI16_bosses)	C++14	0 / 100	1 ms	468 KiB

bosses

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
 
#define ull unsigned long long
#define unint unsigned int
#define sint short int
#define usint unsigned short int
#define ll long long
#define ld long double
#define vt vector
#define pb push_back
#define mp make_pair
#define PI 3.14159265358979323
#define F first
#define S second 
#define all(a) (a).begin(), (a).end()
#define sz(a) ((int)a.size())
#define clr(x,a) memset(x, a, sizeof(x))
#define len(a) ((int)a.length())
#define E 2.7182818284590452353602874713527
#define FOR(i, x) for(int i=0; i<x; ++i)
#define For(i, x) for(auto& i: x)
#define RFOR(i, x) for(int i=x-1; i>=0; --i) 
#define FORS(x, s, e, n) for(int x=s; x<=e; x+=n) 
#define int long long

typedef pair<int, int> pii;
 
void solve(){
    
}

vector<int>adj[5005];
 
int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int a;
    cin >> a;
    int temp;
    for(int x=1;x<=a;x++){
        int b;
        cin >> b;
        for(int y=1;y<=b;y++){
            cin >> temp;
            adj[temp].push_back(x);
        }
    }

    //dfs
    int best=INT_MAX;
    queue<int> q;
    bool visited[5005];
    int distance[5005];
    for(int x=1;x<=a;x++){
        memset(visited,0,sizeof(visited));
        memset(distance,0,sizeof(distance));
        int maxD=0;
        visited[x] = true;
        distance[x] = 0;
        q.push(x);
        while (!q.empty()) {
            int s = q.front(); q.pop();
            // process node s
            for (auto u : adj[s]) {
                if (visited[u]) continue;
                visited[u] = true;
                distance[u] = distance[s]+1;
                maxD=max(maxD,distance[u]);
                q.push(u);
            }
        }
        int counter=0;
        for(int y=1;y<=a;y++){
            counter+=(maxD-distance[y]+1);
        }
        best=min(best,counter);
    }
    cout << best;
    return 0;
}

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