Submission #272883

#TimeUsernameProblemLanguageResultExecution timeMemory
272883toonewbieBosses (BOI16_bosses)C++17
100 / 100
858 ms760 KiB
#pragma GCC optimize("Ofast") #include <bits/stdc++.h> #define F first #define S second #define pb push_back #define endl '\n' #define ll long long #define pi pair<int,int> using namespace std; const int MOD = 1e9 + 7; const int N = 5005; int n; vector<int> g[N]; int used[N], sz[N]; int get(int rt) { for (int i = 1; i <= n; i++) { used[i] = 0; sz[i] = -1; } queue<int> q; q.push(rt); used[rt] = 1; sz[rt] = 1; while(!q.empty()) { int cur = q.front(); q.pop(); for (int i : g[cur]) { if (used[i] == 0) { used[i] = 1; q.push(i); sz[i] = sz[cur] + 1; } } } int res = 0; for (int i = 1; i <= n; i++) { if (sz[i] == -1) return -1; res += sz[i]; } return res; } int main() { ios_base :: sync_with_stdio(0); cin.tie(0); cin >> n; for (int i = 1, c, x; i <= n; i++) { cin >> c; while(c--) cin >> x, g[x].pb(i); } int res = MOD; for (int i = 1; i <= n; i++) { int cur = get(i); if (cur != -1) res = min(res, cur); } cout << res << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...