# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
532996 | 2022-03-04T10:23:15 Z | makanhulia | Bosses (BOI16_bosses) | C++17 | 1 ms | 460 KB |
#include <bits/stdc++.h> using namespace std; #define ll long long int n; vector<int> adj[5005]; int dist[5005][5005]; bool vis[5005][5005]; int bfs(int x) { queue <int> q; q.push(x); int sum = 1; dist[x][x] = 1; int mx = 0; vis[x][x] = true; while(!q.empty()) { int cur = q.front(); q.pop(); for(int i = 0; i < adj[cur].size(); i++) { int next = adj[cur][i]; if (!vis[next][x]) { vis[next][x] = true; dist[next][x] = dist[cur][x] + 1; sum += dist[next][x]; mx = max(mx, dist[next][x]); q.push(next); } } } int ret = (n * (mx + 1)) - sum; return ret; } int main() { cin >> n; for(int i = 1; i <= n; i++) { int k; cin >> k; for(int j = 0; j < k; j++) { int next; cin >> next; adj[next].push_back(i); } } int mn = 1e9; for(int i = 1; i <= n; i++) { mn = min(mn, bfs(i)); } cout << mn << endl; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 332 KB | Output is correct |
2 | Incorrect | 1 ms | 460 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 332 KB | Output is correct |
2 | Incorrect | 1 ms | 460 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 332 KB | Output is correct |
2 | Incorrect | 1 ms | 460 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |