제출 #1075772

#제출 시각아이디문제언어결과실행 시간메모리
1075772MighilonBosses (BOI16_bosses)C++17
22 / 100
1 ms348 KiB
#include <bits/stdc++.h> using namespace std; #ifdef DEBUG #include "../Library/debug.h" #else #define dbg(x...) #endif typedef long long ll; typedef long double ld; typedef pair<int, int> pi; typedef pair<ll, ll> pl; typedef vector<int> vi; typedef vector<ll> vl; typedef vector<pi> vpi; typedef vector<pl> vpl; #define FOR(i, a, b) for (int i = (a); i < (b); ++i) #define F0R(i, a) for (int i = 0; i < (a); ++i) #define FORd(i, a, b) for (int i = (b) - 1; i >= (a); --i) #define F0Rd(i, a) for (int i = (a) - 1; i >= 0; --i) #define trav(a, x) for (auto& a : x) #define f first #define s second #define pb push_back #define sz(x) (int)(x).size() #define all(x) x.begin(), x.end() const char nl = '\n'; const int INF = 1e9; const int MOD = 1e9 + 7; vector<vi> adj; vector<bool> vis; vl a; int n; bool bfs(int x){ vi child(n); vi par(n), layer(n); par[x] = x; queue<pi> q; q.push({x, 0}); vis[x] = true; while(!q.empty()){ auto [u, i] = q.front(); layer[u] = i; q.pop(); trav(v, adj[u]){ if(!vis[v]){ vis[v] = true; par[v] = u; child[u]++; q.push({v, i + 1}); } } } if(accumulate(all(vis), 0) != n) return false; vis.assign(n, false); priority_queue<pi> pq; F0R(i, n){ if(child[i] == 0){ pq.push({layer[i], i}); vis[i] = true; } } while(!pq.empty()){ auto [j, i] = pq.top(); pq.pop(); if(par[i] == i) continue; a[par[i]] += a[i]; if(vis[par[i]] == false) pq.push({layer[par[i]], par[i]}), vis[par[i]] = true; } if(accumulate(all(vis), 0) != n) return false; return true; } void solve(){ cin >> n; adj.resize(n); vis.resize(n); a.resize(n); F0R(i, n){ int x; cin >> x; F0R(j, x){ int a; cin >> a; a--; adj[a].pb(i); } } int size = 0; F0R(i, n) size = max(size, (int)adj[i].size()); ll mn = 1e18; F0R(i, n){ if(sz(adj[i]) != size) continue; vis.assign(n, false); a.assign(n, 1); if(!bfs(i)) continue; dbg(a) mn = min(mn, accumulate(all(a), 0LL)); } cout << mn << nl; } int32_t main(){ ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int TC = 1; // cin >> TC; while(TC--){ solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...