Submission #1162209

#TimeUsernameProblemLanguageResultExecution timeMemory
1162209LilPlutonBosses (BOI16_bosses)C++20
100 / 100
415 ms31936 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define ar array #define all(x) x.begin(), x.end() #define sortall(x) sort(all(x)) #define rep(i,a,b) for(int i = a; i < b; i++) #define per(i,a,b) for(int i = a; i >= b; i--) #define trav(a,x) for(auto& a : x) #define sz(x) (int)(x).size() #define ff first #define ss second #define pb push_back #define mp make_pair #define endl '\n' #define debug(x) cerr << #x << " = " << x << endl const int N = 1e6 + 5; struct BIT{ int n; vector<int>ft; void init(int _n){ n = _n; ft.resize(n + 1); } void update(int x, int val){ for(; x <= n; x += x & -x){ ft[x] += val; } } int query(int x){ int res = 0; for(; x > 0; x -= x & -x){ res += ft[x]; } return res; } int get(int l,int r){ return query(r) - query(l - 1); } }; struct DSU{ int n; vector<int> par, siz; void init(int _n){ n = _n + 5; par.resize(n); siz.resize(n); iota(all(par), 0); fill(all(siz), 1); } int find(int x){ return x == par[x] ? x : par[x] = find(par[x]); } void unite(int x, int y){ x = find(x); y = find(y); if(x != y){ if(siz[x] < siz[y]) swap(x, y); par[y] = x; siz[x] += siz[y]; } } }; vector<int>adj[N]; vector<int>dis(N); void solve(){ int ans = INT_MAX; int n; cin >> n; rep(i, 0, n){ int m; cin >> m; rep(j, 0, m){ int x; cin >> x; adj[--x].push_back(i); } } rep(nt, 0, n){ rep(j, 0, n){ dis[j] = INT_MAX; } queue<int>q; q.push(nt); dis[nt] = 1; while(!q.empty()){ int u = q.front(); q.pop(); for(auto v : adj[u]){ if(dis[v] == INT_MAX){ dis[v] = dis[u] + 1; q.push(v); } } } int cn = 0; rep(j, 0, n){ cn += dis[j]; } ans = min(ans, cn); } cout << ans << endl; } signed main() { ios::sync_with_stdio(0); cin.tie(0); int T = 1; while(T--){ solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...