# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
725560 | 2023-04-17T16:28:18 Z | Bogdan1110 | Bosses (BOI16_bosses) | C++14 | 1060 ms | 1012 KB |
#include <bits/stdc++.h> #define FAST {ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);} #define FILES {freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);} #define ll long long #define ull unsigned long long #define pqueue priority_queue #define pb push_back #define fi first #define se second #define ld long double #define pii pair<int,int> #define pll pair<long long,long long> #define all(a) (a).begin(), (a).end() #define mp make_pair using namespace std; // order_of_key -> # less than k // find_by_order -> k-th element // pq max element void files() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif } const double eps = 0.00000001; const int NMAX = 5050; const ll inf = LLONG_MAX/3; const ll modi = 998244353; vector<int>al[NMAX]; vector<int>al1[NMAX]; int visited[NMAX]; ll res = 0; int n; void fun(int node){ queue<pii> q; q.push({node,0}); vector<int>ord; while(!q.empty()){ int nd = q.front().fi; int pret = q.front().se; q.pop(); if ( visited[nd] ) { continue; } ord.pb(nd); al1[pret].pb(nd); visited[nd] = 1; for (auto u : al[nd]) { q.push({u,nd}); } } reverse(all(ord)); for (auto nd : ord){ for (auto u : al1[nd]) { visited[nd]+= visited[u]; } res += visited[nd]; } for (int i = 0 ; i <= n ; i++ ) { al1[i].clear(); } } void solve() { cin >> n; for (int i = 1 ; i <= n ; i++ ) { int k; cin >> k; for (int j = 0 ; j < k ; j++ ) { int a; cin >> a; al[a].pb(i); } } ll ans = LLONG_MAX; for (int i = 1 ; i <= n ; i++ ) { memset(visited,0,sizeof(visited)); res = 0; fun(i); for (int j = 1 ; j <= n ; j++ ){ if ( visited[j] == 0 ) res = LLONG_MAX; } ans = min(ans,res); } cout << ans << endl; } int main () { FAST int t=1; /* cin >> t; //*/ int i = 1; while(t--) { //cout << "Case #" << i++ << ": " ; solve(); } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 468 KB | Output is correct |
2 | Correct | 1 ms | 468 KB | Output is correct |
3 | Correct | 1 ms | 564 KB | Output is correct |
4 | Correct | 1 ms | 468 KB | Output is correct |
5 | Correct | 1 ms | 468 KB | Output is correct |
6 | Correct | 1 ms | 468 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 468 KB | Output is correct |
2 | Correct | 1 ms | 468 KB | Output is correct |
3 | Correct | 1 ms | 564 KB | Output is correct |
4 | Correct | 1 ms | 468 KB | Output is correct |
5 | Correct | 1 ms | 468 KB | Output is correct |
6 | Correct | 1 ms | 468 KB | Output is correct |
7 | Correct | 1 ms | 564 KB | Output is correct |
8 | Correct | 1 ms | 468 KB | Output is correct |
9 | Correct | 1 ms | 468 KB | Output is correct |
10 | Correct | 1 ms | 468 KB | Output is correct |
11 | Correct | 1 ms | 468 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 468 KB | Output is correct |
2 | Correct | 1 ms | 468 KB | Output is correct |
3 | Correct | 1 ms | 564 KB | Output is correct |
4 | Correct | 1 ms | 468 KB | Output is correct |
5 | Correct | 1 ms | 468 KB | Output is correct |
6 | Correct | 1 ms | 468 KB | Output is correct |
7 | Correct | 1 ms | 564 KB | Output is correct |
8 | Correct | 1 ms | 468 KB | Output is correct |
9 | Correct | 1 ms | 468 KB | Output is correct |
10 | Correct | 1 ms | 468 KB | Output is correct |
11 | Correct | 1 ms | 468 KB | Output is correct |
12 | Correct | 26 ms | 764 KB | Output is correct |
13 | Correct | 20 ms | 804 KB | Output is correct |
14 | Correct | 326 ms | 828 KB | Output is correct |
15 | Correct | 40 ms | 724 KB | Output is correct |
16 | Correct | 1012 ms | 980 KB | Output is correct |
17 | Correct | 1060 ms | 1012 KB | Output is correct |
18 | Correct | 1053 ms | 1008 KB | Output is correct |