# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
39423 | 2018-01-15T03:30:13 Z | WhipppedCream | Bosses (BOI16_bosses) | C++14 | 0 ms | 2252 KB |
#include <bits/stdc++.h> //#ifdef atom #else #endif using namespace std; typedef long long ll; typedef pair<int, int> ii; #define X first #define Y second #define vi vector<int> #define vvi vector< vi > #define vii vector< ii > #define mp make_pair #define pb push_back const int maxn = 5005; vector<int> adj[maxn]; int n; int vis[maxn]; int vis2[maxn]; int p[maxn]; int inq[maxn]; ll cost[maxn]; ll solve(int x) { memset(vis, 0, sizeof vis); memset(vis2, 0, sizeof vis2); memset(cost, 0, sizeof cost); memset(p, -1, sizeof p); memset(inq, 0, sizeof inq); queue<int> Q; Q.push(x); vis2[x] = vis[x] = 1; while(!Q.empty()) { int u = Q.front(); Q.pop(); for(int v : adj[u]) { if(!vis2[v]) { vis[u] = 1; vis2[v] = 1; p[v] = u; Q.push(v); } } } //for(int i = 1; i<= n; i++) printf("%d ", p[i]); //printf("\n"); for(int i = 1; i<= n; i++) if(!vis[i]) Q.push(i); while(!Q.empty()) { int u = Q.front(); Q.pop(); cost[u]++; if(p[u] == -1) continue; cost[p[u]] += cost[u]; if(!inq[p[u]]) { Q.push(p[u]); inq[p[u]] = 1; } } ll total = 0; //for(int i = 1; i<= n; i++) printf("%d ", cost[i]); //printf("\n"); for(int i = 1; i<= n; i++) total += cost[i]; return total; } int main() { //#ifndef atom //freopen(".in", "r", stdin); //freopen(".out", "w", stdout); //#endif scanf("%d", &n); for(int i = 1; i<= n; i++) { int k; scanf("%d", &k); for(int j = 1; j<= k; j++) { int x; scanf("%d", &x); adj[x].pb(i); } } ll best = 1e18; for(int i = 1; i<= n; i++) best = min(best, solve(i)); printf("%lld\n", best); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 2252 KB | Output is correct |
2 | Correct | 0 ms | 2252 KB | Output is correct |
3 | Incorrect | 0 ms | 2252 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 2252 KB | Output is correct |
2 | Correct | 0 ms | 2252 KB | Output is correct |
3 | Incorrect | 0 ms | 2252 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 2252 KB | Output is correct |
2 | Correct | 0 ms | 2252 KB | Output is correct |
3 | Incorrect | 0 ms | 2252 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |