Submission #350789

#	Time	Username	Problem	Language	Result	Execution time	Memory
350789		Hossein8320	Bosses (BOI16_bosses)	C++17	0 / 100	1 ms	620 KiB

bosses

// That's what she said !
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
const int maxn = 5e3 + 9 , modn = 1e9 + 7;
int n, v, k, ans = 1e18, cnt[maxn], h[maxn];
bool mark[maxn];
vector <int> adj[maxn], adj2[maxn];
int bfs(int v)
{
    queue <int> q;
    int H = 0, sum = 0, g = 0;
    mark[v] = 1;
    cnt[0] = 1;
    q.push(v);
    while(q.size()){
        v = q.front();
        q.pop();
        for(auto i : adj[v]){
            if(mark[i])
                continue;
            h[i] = h[v] + 1;
            cnt[h[i]]++;
            H = max(H , h[i]);
            mark[i] = 1;
            q.push(i);
        }
    }
    for(int i = H; i > -1; i--){
        g += cnt[i];
        sum += g;
    }
    for(int i = 1; i <= n; i++)
        if(!mark[i])
            return -1;
    return sum;
}
int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n;
	for(int i = 1; i <= n; i++){
        cin >> k;
        for(int j = 0; j < k; j++){
            cin >> v;
            adj[v].push_back(i);
            adj2[v].push_back(i);
            adj[i].push_back(v);
        }
	}
    for(int i = 1; i <= n; i++){
        swap(adj[i], adj2[i]);
        int p = bfs(i);
        swap(adj[i], adj2[i]);
        if(p != -1)
            ans = min(ans , p);
        for(int i = 0; i <= n; i++){
            cnt[i] = h[i] = 0;
            mark[i] = 0;
        }
    }
    cout << ans;
	return 0;
}

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