oj.uz

Submission #829730

# Submission time Handle Problem Language Result Execution time Memory
829730 2023-08-18T14:37:05 Z DP_196 Bosses (BOI16_bosses) C++14
100 / 100
 898 ms 676 KB 
#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

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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 440 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 440 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 448 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 440 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 448 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 5 ms 576 KB Output is correct
13 Correct 4 ms 468 KB Output is correct
14 Correct 91 ms 600 KB Output is correct
15 Correct 14 ms 580 KB Output is correct
16 Correct 427 ms 640 KB Output is correct
17 Correct 898 ms 676 KB Output is correct
18 Correct 880 ms 672 KB Output is correct