Submission #973826

#TimeUsernameProblemLanguageResultExecution timeMemory
973826Halym2007Bosses (BOI16_bosses)C++17
0 / 100
1 ms604 KiB
#include <bits/stdc++.h> using namespace std; const int N = 2e2 + 5; #define ll long long #define pb push_back #define sz size() map <int, int> mp[N]; int n, val[N][N], sub[N], vis[N]; vector <int> v[N], p[N]; void solve (int x, int pr) { for (int i : p[x]) { if (i == pr) continue; solve (i, x); sub[x] += sub[i]; } sub[x]++; } int root(int x) { queue <int> q; for (int i = 1; i <= n; ++i) { vis[i] = 0; sub[i] = 0; p[i].clear(); } q.push(x); vis[x] = 1; while (!q.empty()) { int x = q.front(); q.pop(); for (int i : v[x]) { if (vis[i]) continue; p[x].pb (i); vis[i] = 1; q.push(i); } } for (int i = 1; i <= n; ++i) { if (!vis[i]) return -1; } solve (x, -1); int ret = 0; for (int i = 1; i <= n; ++i) { ret += sub[i]; } return ret; } int main () { // freopen ("input.txt", "r", stdin); cin >> n; for (int i = 1; i <= n; ++i) { int k; cin >> k; for (int j = 1; j <= k; ++j) { cin >> val[i][j]; mp[i][val[i][j]] = 1; v[val[i][j]].pb (i); } } int jog = 1e9; for (int i = 1; i <= n; ++i) { int jj = root (i); assert (jj != -1); if (~jj) { jog = min (jog, jj); } } cout << jog; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...