oj.uz

Submission #334996

# Submission time Handle Problem Language Result Execution time Memory
334996 2020-12-10T17:20:08 Z limabeans Bosses (BOI16_bosses) C++17
100 / 100
 1298 ms 24172 KB 
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;

const ll inf = 1e18;
const int maxn = 1e6 + 5;



int n;
vector<int> g[maxn];


int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    
    cin>>n;
    for (int i=1; i<=n; i++) {
	int k;
	cin>>k;
	while (k--) {
	    int p;
	    cin>>p;
	    g[p].push_back(i);
	}
    }

    ll ans = inf;

    for (int r=1; r<=n; r++) {
	vector<int> par(n+1,-1);
	vector<int> deg(n+1,0);
	par[r]=r;
	queue<int> qq;
	qq.push(r);
	while (qq.size()) {
	    int at=qq.front();
	    qq.pop();
	    for (int to: g[at]) {
		if (par[to]==-1) {
		    par[to]=at;
		    deg[at]++;
		    qq.push(to);
		}
	    }
	}
	bool ok = true;
	for (int i=1; i<=n && ok; i++) {
	    if (par[i]==-1) ok=false;
	}

	if (ok) {
	    while (qq.size()) qq.pop();
	    ll cur = 0;
	    vector<ll> sum(n+1,0);
	    for (int i=1; i<=n; i++) {
		if (deg[i]==0) qq.push(i);
	    }
	    while (qq.size()) {
		int at = qq.front();
		qq.pop();
		sum[at]++;
		cur += sum[at];
		if (par[at]!=at) {
		    int p=par[at];
		    sum[p] += sum[at];
		    if (--deg[p]==0) {
			qq.push(p);
		    }
		}
	    }
	    ans = min(ans, cur);
	}
    }



    cout<<ans<<endl;    
    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23788 KB Output is correct
2 Correct 18 ms 23788 KB Output is correct
3 Correct 16 ms 23788 KB Output is correct
4 Correct 16 ms 23788 KB Output is correct
5 Correct 17 ms 23788 KB Output is correct
6 Correct 16 ms 23788 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23788 KB Output is correct
2 Correct 18 ms 23788 KB Output is correct
3 Correct 16 ms 23788 KB Output is correct
4 Correct 16 ms 23788 KB Output is correct
5 Correct 17 ms 23788 KB Output is correct
6 Correct 16 ms 23788 KB Output is correct
7 Correct 16 ms 23788 KB Output is correct
8 Correct 17 ms 23788 KB Output is correct
9 Correct 16 ms 23788 KB Output is correct
10 Correct 17 ms 23788 KB Output is correct
11 Correct 17 ms 23788 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23788 KB Output is correct
2 Correct 18 ms 23788 KB Output is correct
3 Correct 16 ms 23788 KB Output is correct
4 Correct 16 ms 23788 KB Output is correct
5 Correct 17 ms 23788 KB Output is correct
6 Correct 16 ms 23788 KB Output is correct
7 Correct 16 ms 23788 KB Output is correct
8 Correct 17 ms 23788 KB Output is correct
9 Correct 16 ms 23788 KB Output is correct
10 Correct 17 ms 23788 KB Output is correct
11 Correct 17 ms 23788 KB Output is correct
12 Correct 25 ms 23892 KB Output is correct
13 Correct 20 ms 23916 KB Output is correct
14 Correct 172 ms 24044 KB Output is correct
15 Correct 44 ms 24064 KB Output is correct
16 Correct 633 ms 24056 KB Output is correct
17 Correct 1298 ms 24172 KB Output is correct
18 Correct 1283 ms 24172 KB Output is correct