Submission #829730

#	Time	Username	Problem	Language	Result	Execution time	Memory
829730		DP_196	Bosses (BOI16_bosses)	C++14	100 / 100	898 ms	676 KiB

bosses

#include <bits/stdc++.h>

using namespace std;

#define sz(x) (int)x.size()
#define MASK(i) ((1LL) << (i))
#define all(x) x.begin(), x.end()
#define BIT(x, i) ((x) >> (i) & (1LL))
#define dbg(...) cerr << "#" << __LINE__ << ":[" << #__VA_ARGS__ \
<< "] = [" ,DBG(__VA_ARGS__)

string to_string(const string& s) { return '"' + s + '"'; }
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
        cerr << to_string(h); if(sizeof...(t)) cerr << ", "; DBG(t...);
}

template <class T>
inline bool maximize(T &a, const T &b) { return (a < b ? (a = b) : 0); }
template <class T>
inline bool minimize(T &a, const T &b) { return (a > b ? (a = b) : 0); }

const int MAXN = 2e5 + 6;
const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;

int n, d[5005];
bool vis[5005];
vector<int> adj[5005];

void dfs(int u) {
	vis[u] = true;
	for (auto v : adj[u]) if (!vis[v]) dfs(v);
}

void solve() {
	cin >> n;
	
	for (int i = 1; i <= n; i++) {
		int k, x;
		cin >> k;
		for (int j = 1; j <= k; j++) {
			cin >> x;
			adj[x].push_back(i);
		}
	}
	
	int res = 1e16;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) vis[j] = false;
		dfs(i);
		bool ok = true;
		for (int j = 1; j <= n; j++) if (!vis[j]) ok = false;
		if (!ok) continue;
		for (int j = 1; j <= n; j++) d[j] = -1;
		
		queue<int> pq;
		d[i] = 1;
		pq.push(i);
		
		int sum = 1;
		
		while (sz(pq)) {
			int u = pq.front();
			pq.pop();
			
			for (auto v : adj[u]) {
				if (d[v] != -1) continue;
				d[v] = d[u] + 1;
				sum += d[v];
				pq.push(v);
			}
		}			
		
		minimize(res, sum);
	}
	
	cout << res;
}

#define TASK ""
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen(TASK".inp", "r", stdin);
    //freopen(TASK".out", "w", stdout);

    int ntest = 1;
    //cin >> ntest;
    while (ntest--) solve();

    return 0;
}
//612

Compilation message (stderr)

bosses.cpp: In function 'void solve()':
bosses.cpp:48:12: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+16' to '2147483647' [-Woverflow]
   48 |  int res = 1e16;
      |            ^~~~

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