Submission #1074682

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074682		dosts	Bosses (BOI16_bosses)	C++17	100 / 100	526 ms	856 KiB

bosses

//Dost SEFEROĞLU
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<    
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>
const int MOD = 1e9+7,inf = 2e12;
const int N = 5001;
vi edges[N];
int n;

int bfs(int root) {
    queue<int> q;
    vi vis(n+1,inf);
    int ret = 0;
    vis[root] = 0;
    q.push(root);
    while (!q.empty()) {
        int f = q.front();
        q.pop();
        for (auto it : edges[f]) {
            if (vis[it] == inf) {
                vis[it] = vis[f]+1;
                ret+=vis[it];
                q.push(it);
            }
        }
    }
    if (*max_element(vis.begin()+1,vis.end()) > n+5) return inf;
    return ret;
}
void solve() { 
    cin >> n;
    for (int i=1;i<=n;i++) {
        int k;
        cin >> k;
        for (int j=1;j<=k;j++) {
            int x;
            cin >> x;
            edges[x].push_back(i);
        }
    }
    int ans = inf;
    for (int i=1;i<=n;i++) {
        int cost = bfs(i);
        ans = min(ans,cost+n);
    }
    cout << ans << endl;
}
 
signed main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t; 
    while (t --> 0) solve();
}

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