# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
973892 | 2024-05-02T12:22:40 Z | KasymK | Bosses (BOI16_bosses) | C++17 | 860 ms | 1264 KB |
#include "bits/stdc++.h" using namespace std; int n; const int N = 5e3 + 5; vector<int> adj[N]; vector<int> taze_adj[N]; int vis[N], node_sany[N]; void dfs(int x){ node_sany[x] = 1; for(auto to : taze_adj[x]){ dfs(to); node_sany[x] += node_sany[to]; } } int kok(int x){ for(int i = 1; i <= n; ++i){ vis[i] = 0; node_sany[i] = 0; taze_adj[i].clear(); } queue<int> q; q.push(x); vis[x] = 1; while(!q.empty()){ int id = q.front(); q.pop(); for(auto to : adj[id]) if(!vis[to]){ vis[to] = 1; taze_adj[id].push_back(to); q.push(to); } } for(int i = 1; i <= n; ++i) if(!vis[i]) return -1; // eger birini hem gormedik bolsam, onda yalnysh bolyar dfs(x); int ret = 0; for(int i = 1; i <= n; ++i) ret += node_sany[i]; return ret; } int main(){ scanf("%d", &n); for(int i = 1; i <= n; ++i){ int K; scanf("%d", &K); while(K--){ int A; scanf("%d", &A); adj[A].push_back(i); } } int ans = INT_MAX; for(int i = 1; i <= n; ++i){ int kk = kok(i); if(~kk) ans = min(ans, kk); } printf("%d\n", ans); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 600 KB | Output is correct |
2 | Correct | 1 ms | 604 KB | Output is correct |
3 | Correct | 1 ms | 604 KB | Output is correct |
4 | Correct | 1 ms | 604 KB | Output is correct |
5 | Correct | 0 ms | 604 KB | Output is correct |
6 | Correct | 0 ms | 604 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 600 KB | Output is correct |
2 | Correct | 1 ms | 604 KB | Output is correct |
3 | Correct | 1 ms | 604 KB | Output is correct |
4 | Correct | 1 ms | 604 KB | Output is correct |
5 | Correct | 0 ms | 604 KB | Output is correct |
6 | Correct | 0 ms | 604 KB | Output is correct |
7 | Correct | 1 ms | 604 KB | Output is correct |
8 | Correct | 1 ms | 604 KB | Output is correct |
9 | Correct | 0 ms | 604 KB | Output is correct |
10 | Correct | 1 ms | 604 KB | Output is correct |
11 | Correct | 1 ms | 604 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 600 KB | Output is correct |
2 | Correct | 1 ms | 604 KB | Output is correct |
3 | Correct | 1 ms | 604 KB | Output is correct |
4 | Correct | 1 ms | 604 KB | Output is correct |
5 | Correct | 0 ms | 604 KB | Output is correct |
6 | Correct | 0 ms | 604 KB | Output is correct |
7 | Correct | 1 ms | 604 KB | Output is correct |
8 | Correct | 1 ms | 604 KB | Output is correct |
9 | Correct | 0 ms | 604 KB | Output is correct |
10 | Correct | 1 ms | 604 KB | Output is correct |
11 | Correct | 1 ms | 604 KB | Output is correct |
12 | Correct | 4 ms | 604 KB | Output is correct |
13 | Correct | 3 ms | 860 KB | Output is correct |
14 | Correct | 149 ms | 860 KB | Output is correct |
15 | Correct | 28 ms | 856 KB | Output is correct |
16 | Correct | 544 ms | 856 KB | Output is correct |
17 | Correct | 860 ms | 1064 KB | Output is correct |
18 | Correct | 850 ms | 1264 KB | Output is correct |