# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
107347 | 2019-04-23T12:09:01 Z | MohamedAhmed0 | Bosses (BOI16_bosses) | C++14 | 1500 ms | 98860 KB |
#include <bits/stdc++.h> using namespace std; const int MAX = 5005 ; int vis[MAX] , par[MAX][MAX] , can[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] = src ; par[src][src] = 0 ; while(!q.empty()) { int node = q.front() ; q.pop() ; cnt++ ; for(auto &child : adj[node]) { if(vis[child] == src) continue ; vis[child] = src ; par[src][child] = node ; q.push(child) ; } } return ; } int src ; void dfs(int node) { for(auto &child : adj[node]) { if(par[src][child] == node) { dfs(child) ; dp[node] += dp[child] ; } } dp[node]++; cost += dp[node] * 1ll; return ; } /*int readint() { char c ; c = getchar() ; while(true) { if(c >= '0' && c <= '9') break ; c = getchar() ; } int result = (c - '0') ; c = getchar() ; while(true) { if(c < '0' || c > '9') break ; result = result * 10 + (c - '0') ; c = getchar() ; } return result ; }*/ 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) { cnt = 0 ; bfs(i) ; if(cnt == n) can[i] = 1 ; } for(int i = 1 ; i <= n ; ++i) { if(can[i] == 0) continue ; memset(dp , 0 , sizeof(dp)) ; src = i ; cnt = 0 , cost = 0; 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 | 2 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 | 512 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 | 2 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 | 512 KB | Output is correct |
6 | Correct | 3 ms | 512 KB | Output is correct |
7 | Correct | 2 ms | 896 KB | Output is correct |
8 | Correct | 3 ms | 640 KB | Output is correct |
9 | Correct | 4 ms | 640 KB | Output is correct |
10 | Correct | 3 ms | 896 KB | Output is correct |
11 | Correct | 4 ms | 896 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 512 KB | Output is correct |
2 | Correct | 2 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 | 512 KB | Output is correct |
6 | Correct | 3 ms | 512 KB | Output is correct |
7 | Correct | 2 ms | 896 KB | Output is correct |
8 | Correct | 3 ms | 640 KB | Output is correct |
9 | Correct | 4 ms | 640 KB | Output is correct |
10 | Correct | 3 ms | 896 KB | Output is correct |
11 | Correct | 4 ms | 896 KB | Output is correct |
12 | Correct | 12 ms | 1572 KB | Output is correct |
13 | Correct | 9 ms | 1280 KB | Output is correct |
14 | Correct | 184 ms | 63608 KB | Output is correct |
15 | Correct | 38 ms | 41216 KB | Output is correct |
16 | Correct | 734 ms | 80976 KB | Output is correct |
17 | Execution timed out | 1542 ms | 98860 KB | Time limit exceeded |
18 | Halted | 0 ms | 0 KB | - |