제출 #1089925

#제출 시각아이디문제언어결과실행 시간메모리
1089925NurislamBosses (BOI16_bosses)C++17
0 / 100
1 ms348 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define ff first #define ss second #define all(x) x.begin(),x.end() #define rall(x) x.rbegin(),x.rend() #define int long long template <class F, class _S> bool chmin(F &u, const _S &v){ bool flag = false; if ( u > v ){ u = v; flag |= true; } return flag; } template <class F, class _S> bool chmax(F &u, const _S &v){ bool flag = false; if ( u < v ){ u = v; flag |= true; } return flag; } constexpr long double EPS = 1e-12; const int N = 1e6+50, inf = 1e17; //int mod = 998244353 //int mod = 1000000007; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define rnd(l, r) uniform_int_distribution <int> (l, r)(rng) void solve(){ int n; cin >> n; vector<vector<int>> g(n+1); for(int i = 1; i <= n; i++){ int sz; cin >> sz; while(sz--){ int to; cin >> to; g[to].pb(i); } } vector<int> us(n+5, 0); auto bfs = [&](int ps) -> int{ queue<int> q; q.push(ps); us[ps] = n+1; vector<int> al; while(q.size()){ auto t = q.front(); q.pop(); al.pb(t); for(int to:g[t]){ if(us[to])continue; us[to] = t; q.push(to); } }reverse(all(al)); int ans = 0; vector<int> tot(n+1, 0); for(int i:al){ tot[i] ++ ; tot[us[i]] += tot[i]; } for(int &i:us)i = 0; for(int i = 1; i <= n; i++)ans += tot[i]; return ans; }; int ans = inf; for(int i = 1; i <= n; i++){ chmin(ans, bfs(i)); } cout << ans << '\n'; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int tt = 1; //cin >> tt; while(tt--){ solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...