Submission #790902

#	Time	Username	Problem	Language	Result	Execution time	Memory
790902		makanhulia	Bosses (BOI16_bosses)	C++17	100 / 100	399 ms	668 KiB

bosses

#include<bits/stdc++.h>
using namespace std;
#define ioss ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define tup tuple<int, int, int>
#define pii pair<int, int>
#define fi first
#define se second
#define pub push_back
#define pob pop_back
int n;
vector<int> adj[5004];
bool vis[5004];
int dist[5004];
queue<int> q;
int main() {
    ioss;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        int k; cin >> k;
        for(int j = 0; j < k; j++) {
            int a; cin >> a;
            adj[a].pub(i);
        }
    }
    int ans = 1e9;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) vis[j] = 0, dist[j] = 0;
        dist[i] = 1, vis[i] = 1;
        q.push(i);
        while(!q.empty()) {
            int u = q.front();
            q.pop();
            for(auto v : adj[u]) {
                if(!vis[v]) {
                    vis[v] = 1;
                    dist[v] = dist[u]+1;
                    q.push(v);
                }
            }
        }
        int cur = 0;
        bool notvis = 0;
        for(int j = 1; j <= n; j++) {
            if(!vis[j]) {
                notvis = 1;
                break;
            }
            cur += dist[j];
        }
        if(notvis) continue;
        ans = min(ans, cur);
        // cout << " root " << i << " " << cur << " " << ans << endl; 
    }
    cout << ans << endl;
}

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