# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
116633 | 2019-06-13T09:15:05 Z | roseanne_pcy | Bosses (BOI16_bosses) | C++14 | 707 ms | 892 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 vis2[maxn]; int p[maxn]; int inq[maxn]; ll cost[maxn]; ll solve(int x) { memset(vis2, 0, sizeof vis2); memset(cost, 0, sizeof cost); memset(p, -1, sizeof p); vector<int> rev; queue<int> Q; Q.push(x); vis2[x] = 1; while(!Q.empty()) { int u = Q.front(); Q.pop(); rev.pb(u); for(int v : adj[u]) { if(!vis2[v]) { vis2[v] = 1; p[v] = u; Q.push(v); } } } if(rev.size() != n) return 1e18; reverse(rev.begin(), rev.end()); ll tot = 0; for(int i = 0; i< (int) rev.size(); i++) { int u = rev[i]; cost[u]++; tot += cost[u]; if(p[u] != -1) cost[p[u]] += cost[u]; } return tot; } 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 | 2 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 | 3 ms | 512 KB | Output is correct |
5 | Correct | 3 ms | 512 KB | Output is correct |
6 | Correct | 2 ms | 512 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 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 | 3 ms | 512 KB | Output is correct |
5 | Correct | 3 ms | 512 KB | Output is correct |
6 | Correct | 2 ms | 512 KB | Output is correct |
7 | Correct | 2 ms | 512 KB | Output is correct |
8 | Correct | 3 ms | 512 KB | Output is correct |
9 | Correct | 2 ms | 512 KB | Output is correct |
10 | Correct | 3 ms | 512 KB | Output is correct |
11 | Correct | 3 ms | 512 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 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 | 3 ms | 512 KB | Output is correct |
5 | Correct | 3 ms | 512 KB | Output is correct |
6 | Correct | 2 ms | 512 KB | Output is correct |
7 | Correct | 2 ms | 512 KB | Output is correct |
8 | Correct | 3 ms | 512 KB | Output is correct |
9 | Correct | 2 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 | 7 ms | 640 KB | Output is correct |
13 | Correct | 5 ms | 660 KB | Output is correct |
14 | Correct | 158 ms | 760 KB | Output is correct |
15 | Correct | 21 ms | 636 KB | Output is correct |
16 | Correct | 602 ms | 892 KB | Output is correct |
17 | Correct | 706 ms | 888 KB | Output is correct |
18 | Correct | 707 ms | 888 KB | Output is correct |