Submission #1242504

#TimeUsernameProblemLanguageResultExecution timeMemory
1242504altern23Bosses (BOI16_bosses)C++20
100 / 100
751 ms1092 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pii pair<ll, ll> #define fi first #define sec second #define ld long double const int MAXN = 5e3; const ll INF = 1e18; const int MOD = 998244353; const ld eps = 1e-6; vector<ll> boss[MAXN + 5]; ll dist[MAXN + 5], vis[MAXN + 5]; vector<ll> adj[MAXN + 5]; ll sum = 0; void dfs(ll idx){ dist[idx] = 1; for(auto i : adj[idx]){ dfs(i); dist[idx] += dist[i]; } sum += dist[idx]; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int tc = 1; // cin >> tc; for(;tc--;){ ll N; cin >> N; for(int i = 1; i <= N; i++){ ll K; cin >> K; for(int j = 1; j <= K; j++){ ll x; cin >> x; boss[x].push_back(i); } } ll ans = INF; for(int i = 1; i <= N; i++){ for(int j = 1; j <= N; j++){ adj[j].clear(); dist[j] = INF; vis[j] = 0; } queue<ll> q; vis[i] = 1; q.push(i); ll cur = 0; for(;!q.empty();){ auto x = q.front(); q.pop(); cur++; for(auto nxt : boss[x]){ if(!vis[nxt]){ vis[nxt] = 1; adj[x].push_back(nxt); q.push(nxt); } } } if(cur != N) continue; sum = 0; dfs(i); ans = min(ans, sum); } cout << ans << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...