Submission #838885

#TimeUsernameProblemLanguageResultExecution timeMemory
838885vjudge1Bosses (BOI16_bosses)C++17
100 / 100
487 ms664 KiB
// #pragma GCC optimize("O3,unroll-loops") // #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt") #include <bits/stdc++.h> #define int long long #define pb push_back #define ui unsigned int #define ld long double #define pl pair<long long int, long long int> #define boost ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define ff first #define ss second #define sz size() #define all(x) x.begin(), x.end() using namespace std; const int maxn = 1e5 + 11; const int inf = 1e18 + 1; // const int mod = 1e9 + 7; const int mod = 998244353; const int dx[] = {-1, 0, 0, 1, -1, -1, 1, 1}; const int dy[] = {0, -1, 1 , 0, -1, 1, -1, 1}; const double eps = 1e-10; int used[5001]; vector<int> g[5001]; int d[5001]; int cnt; queue<int> q; void dfs(int v) { used[ v ] = 1; q.push( v ); while(q.sz) { int v = q.front(); q.pop(); cnt += d[ v ]; for(auto to : g[ v ]) { if(!used[ to ]) { used[ to ] = 1; d[ to ] = d[ v ] + 1; q.push( to ); } } } } void solve() { int n; cin >> n; for(int i = 1; i <= n; i++) { int k; cin >> k; for(int j = 1; j <= k; j++) { int x; cin >> x; g[ x ].pb( i ); } } int ans = inf; for(int i = 1; i <= n; i++) { cnt = 0; d[ i ] = 1; dfs( i ); for(int j = 1; j <= n; j++) { if(!used[ j ]) { cnt = inf; } used[ j ] = 0; d[ j ] = 0; } ans = min(ans, cnt); } cout << ans; } signed main() { // freopen("sum.in", "r", stdin); // freopen("sum.out", "w", stdout); boost; int tt = 1; // cin >> tt; for(int i = 1; i <= tt; i++) { // cout << "Case " << i << ":\n"; solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...