Submission #1275794

#TimeUsernameProblemLanguageResultExecution timeMemory
1275794itsKiaRashBosses (BOI16_bosses)C++20
100 / 100
748 ms1096 KiB
#include <bits/stdc++.h> using namespace std; // #include <ext/pb_ds/tree_policy.hpp> // #include <ext/pb_ds/assoc_container.hpp> // using namespace __gnu_pbds; // find_by_order order_of_key // template<class T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; typedef long long ll; // #pragma GCC optimize ("O2,unroll-loops") // #pragma GCC optimize ("Ofast") // #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt") #define int ll #define FAST_IO (ios_base::sync_with_stdio(false), cin.tie(NULL)); #define file_init freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #define testc int ttt;cin>>ttt;while(ttt--) #define alll(x) (x).begin(),(x).end() #define pqi priority_queue<pii, vector<pii>, greater<pii>> #define endl '\n' #define pb push_back #define ins insert #define pii pair<int, int> #define ff first #define ss second #define bg begin #define rbg rbegin #define sz size() #define mset(x,y) memset(x,y,sizeof(x)) #define clr clear() #define YES cout<<"YES"<<endl #define NO cout<<"NO"<<endl #define vci vector<int> #define sti set<int> #define nl cout<<'\n' #define upb upper_bound #define lrb lower_bound //ll pw(ll a,ll b){ll res=1;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;} ll gcd(ll a, ll b) { if (b == 0) return a; return gcd(b, a % b);} ll lcm(ll a, ll b) { return (a * b) / gcd(a, b); } const ll inf = 1e18 + 18; const int maxn = 5e3 + 7, mod = 1e9 + 7; //998244353 int n, ans, sum; vci adj[maxn], nei[maxn]; int dp[maxn], par[maxn]; bool vis[maxn]; void bfs(int a){ vis[a] = true; queue<int> q; q.push(a); while(q.sz){ int x = q.front(); q.pop(); for(int item : nei[x]) if(!vis[item]){ vis[item] = true; adj[x].pb(item); q.push(item); } } } void dfs(int u, int par = 0){ dp[u] = 1; for(int v : adj[u]) if(v != par){ dfs(v, u); dp[u] += dp[v]; } sum += dp[u]; } int32_t main(){ FAST_IO cin >> n ; ans = inf; for(int i = 1, k ; i <= n ; i ++){ cin >> k ; for(int j = 1, ki ; j <= k ; j ++){ cin >> ki ; nei[ki].pb(i); } } for(int i = 1 ; i <= n ; i ++){ mset(vis, 0); mset(par, 0); mset(dp, 0); sum = 0; for(int j = 1 ; j <= n ; j ++) adj[j].clr; bfs(i); bool flag = true; for(int j = 1 ; j <= n ; j ++) if(!vis[j]) {flag = false; break;} if(!flag) continue; dfs(i); ans = min(ans, sum); } cout << ans << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...