| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 531067 | Majed | Bosses (BOI16_bosses) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define quick ios::sync_with_stdio(0);cin.tie(NULL); cout.tie(NULL);
typedef long long ll;
using namespace std;
const int N = 5001;
bool vis[N] = {false};
// bool prime[N+1];
vector<int>adj[N];
vector<int>v;
map<int,int>mp;
void bfs(int s) {
v.clear();
memset(vis,false,sizeof(vis));
queue<int>q;
vis[s] = true;
q.push(s);
v.push_back(s);
while (!q.empty()) {
int node = q.front();
q.pop();
for (int child : adj[node]) {
if (!vis[child]) {
vis[child] = true;
q.push(child);
v.push_back(child);
}
}
}
}
int main() {
quick;
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
int k;
cin >> k;
for (int j = 0; j < k; j++) {
int u;
cin >> u;
adj[u].push_back(i);
// adj[i].push_back(u);
}
}
ll mn = LLONG_MAX;
ll sum;
for (int i = 1; i <= n; i++) {
int c = 0, sum = 0;
bfs(i);
mp.clear();
if (v.size() != n)
continue;
reverse(all(v));
memset(vis,false,sizeof(vis));
for (int i = 0; i < v.size(); i++) {
vis[v[i]] = true;
for (int child : adj[v[i]]) {
if (vis[child]) {
mp[v[i]] += mp[child];
}
}
mp[v[i]]++;
sum += mp[v[i]];
}
mn = min(sum,mn);
}
cout << mn << endl;
// while (!root.empty()) {
// queue<int>q;
// int level[N];
// memset(level,0,sizeof(level));
//
//
// int u = root.front();
// q.push(u);
// level[u] = 1;
// vis[u] = true;
//
// while (!q.empty()) {
// int node = q.front();
// q.pop();
// for (int child : adj[node]) {
// if (!vis[child]) {
// vis[child] = true;
// q.push(child);
// level[child] = level[node] + 1;
// mx = max(mx, level[child]);
// }
// }
// }
// root.pop();
// }
// cout << mx << endl;
}