# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
341306 | 2020-12-29T11:49:33 Z | AlexNeagu | Bosses (BOI16_bosses) | C++14 | 1219 ms | 876 KB |
#include<bits/stdc++.h> // #define int long long #pragma GCC target ("avx2") #pragma GCC optimization ("O3") #pragma GCC optimization ("unroll-loops") #define pb push_back #define mp make_pair using namespace std; typedef long long ll; typedef long double ld; typedef pair<ll,ll> pi; const int mod = 1e9 + 9; const int N = 106 * 106; const int nax = 1e6+6; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int n; ll ans = 2e18; vector<int> possible_childs[5005]; ll root(int x) { queue<int> Q; Q.push(x); vector<int> d(n + 1, 2e9), p(n + 1); vector<ll> cnt(n + 1, 1LL); vector<int> ord; d[x] = 0; while(Q.size()) { int node = Q.front(); ord.pb(node); Q.pop(); for(auto it : possible_childs[node]) { if(d[node] + 1 < d[it]) { d[it] = d[node] + 1; Q.push(it); p[it] = node; } } } for(int i = 1; i <= n; i++) if(d[i] == 2e9) return 2e18; reverse(ord.begin(), ord.end()); ll sol = 0; for(auto it : ord) { sol += cnt[it]; if(it != x) { cnt[p[it]] += cnt[it]; } } return sol; } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n; for(int i = 1; i <= n; i++) { int len; cin >> len; for(int j = 1; j <= len; j++) { int x; cin >> x; possible_childs[x].push_back(i); } } for(int i = 1; i <= n; i++) { ans = min(ans, root(i)); } cout << ans << '\n'; return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 492 KB | Output is correct |
2 | Correct | 1 ms | 492 KB | Output is correct |
3 | Correct | 1 ms | 492 KB | Output is correct |
4 | Correct | 1 ms | 492 KB | Output is correct |
5 | Correct | 1 ms | 492 KB | Output is correct |
6 | Correct | 1 ms | 492 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 492 KB | Output is correct |
2 | Correct | 1 ms | 492 KB | Output is correct |
3 | Correct | 1 ms | 492 KB | Output is correct |
4 | Correct | 1 ms | 492 KB | Output is correct |
5 | Correct | 1 ms | 492 KB | Output is correct |
6 | Correct | 1 ms | 492 KB | Output is correct |
7 | Correct | 1 ms | 492 KB | Output is correct |
8 | Correct | 1 ms | 492 KB | Output is correct |
9 | Correct | 1 ms | 492 KB | Output is correct |
10 | Correct | 1 ms | 492 KB | Output is correct |
11 | Correct | 1 ms | 492 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 492 KB | Output is correct |
2 | Correct | 1 ms | 492 KB | Output is correct |
3 | Correct | 1 ms | 492 KB | Output is correct |
4 | Correct | 1 ms | 492 KB | Output is correct |
5 | Correct | 1 ms | 492 KB | Output is correct |
6 | Correct | 1 ms | 492 KB | Output is correct |
7 | Correct | 1 ms | 492 KB | Output is correct |
8 | Correct | 1 ms | 492 KB | Output is correct |
9 | Correct | 1 ms | 492 KB | Output is correct |
10 | Correct | 1 ms | 492 KB | Output is correct |
11 | Correct | 1 ms | 492 KB | Output is correct |
12 | Correct | 6 ms | 492 KB | Output is correct |
13 | Correct | 6 ms | 492 KB | Output is correct |
14 | Correct | 216 ms | 748 KB | Output is correct |
15 | Correct | 42 ms | 620 KB | Output is correct |
16 | Correct | 756 ms | 876 KB | Output is correct |
17 | Correct | 1205 ms | 876 KB | Output is correct |
18 | Correct | 1219 ms | 876 KB | Output is correct |