# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
107343 | 2019-04-23T11:51:08 Z | MohamedAhmed0 | Bosses (BOI16_bosses) | C++14 | 1500 ms | 768 KB |
#include <bits/stdc++.h> using namespace std; const int MAX = 5005 ; int vis[MAX] , par[MAX]; long long dp[MAX] , cost = 0; vector< vector<int> >adj(MAX) ; int n , cnt = 0 ; void bfs(int src) { queue<int>q ; q.push(src) ; vis[src] = 1 ; par[src] = 0 ; while(!q.empty()) { int node = q.front() ; q.pop() ; cnt++ ; for(auto &child : adj[node]) { if(vis[child] == 1) continue ; vis[child] = 1 ; par[child] = node ; q.push(child) ; } } return ; } void dfs(int node) { for(auto &child : adj[node]) { if(par[child] == node) { dfs(child) ; dp[node] += dp[child] ; } } dp[node]++; cost += dp[node] * 1ll; return ; } int main() { scanf("%d" , &n) ; for(int i = 1 ; i <= n ; ++i) { int m ; scanf("%d" , &m) ; while(m--) { int x ; scanf("%d" , &x) ; adj[x].push_back(i) ; } } long long ans = 1e18 ; for(int i = 1 ; i <= n ; ++i) { memset(vis , 0 , sizeof(vis)) ; memset(dp , 0 , sizeof(dp)) ; memset(par , 0 , sizeof(par)) ; cnt = 0 , cost = 0; bfs(i) ; if(cnt != n) continue; dfs(i) ; ans = min(ans , cost) ; } return printf("%lld" , ans) , 0 ; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 512 KB | Output is correct |
2 | Correct | 3 ms | 512 KB | Output is correct |
3 | Correct | 2 ms | 512 KB | Output is correct |
4 | Correct | 2 ms | 512 KB | Output is correct |
5 | Correct | 2 ms | 484 KB | Output is correct |
6 | Correct | 3 ms | 512 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 512 KB | Output is correct |
2 | Correct | 3 ms | 512 KB | Output is correct |
3 | Correct | 2 ms | 512 KB | Output is correct |
4 | Correct | 2 ms | 512 KB | Output is correct |
5 | Correct | 2 ms | 484 KB | Output is correct |
6 | Correct | 3 ms | 512 KB | Output is correct |
7 | Correct | 2 ms | 512 KB | Output is correct |
8 | Correct | 2 ms | 512 KB | Output is correct |
9 | Correct | 3 ms | 512 KB | Output is correct |
10 | Correct | 3 ms | 512 KB | Output is correct |
11 | Correct | 3 ms | 512 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 512 KB | Output is correct |
2 | Correct | 3 ms | 512 KB | Output is correct |
3 | Correct | 2 ms | 512 KB | Output is correct |
4 | Correct | 2 ms | 512 KB | Output is correct |
5 | Correct | 2 ms | 484 KB | Output is correct |
6 | Correct | 3 ms | 512 KB | Output is correct |
7 | Correct | 2 ms | 512 KB | Output is correct |
8 | Correct | 2 ms | 512 KB | Output is correct |
9 | Correct | 3 ms | 512 KB | Output is correct |
10 | Correct | 3 ms | 512 KB | Output is correct |
11 | Correct | 3 ms | 512 KB | Output is correct |
12 | Correct | 10 ms | 612 KB | Output is correct |
13 | Correct | 8 ms | 640 KB | Output is correct |
14 | Correct | 127 ms | 760 KB | Output is correct |
15 | Correct | 21 ms | 640 KB | Output is correct |
16 | Correct | 584 ms | 724 KB | Output is correct |
17 | Execution timed out | 1552 ms | 768 KB | Time limit exceeded |
18 | Halted | 0 ms | 0 KB | - |