# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
636953 | BidoTeima | Bosses (BOI16_bosses) | C++17 | 2 ms | 724 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.
/// isA AC
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<typename t1>
using ordered_set = tree<t1, null_type,less<t1>, rb_tree_tag,tree_order_statistics_node_update>;
using ll = long long;
void moo(string filename);
void ACPLS(string str = "")
{
if(str=="NOF")return;
if(str.size())
moo(str);
else{
#ifndef ONLINE_JUDGE
freopen("output.txt", "w", stdout);
freopen("input.txt", "r", stdin);
#endif
}
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
void moo(string fileName){
freopen((fileName+".in").c_str(),"r",stdin);
freopen((fileName+".out").c_str(),"w",stdout);
}
#define tc \
int tttttt,subtask; \
cin >> tttttt /*>> subtask*/; \
while (tttttt--)
#define sumrange(l, r, arr) (l == 0 ? arr[r] : arr[r] - arr[l - 1])
#define all(v) v.begin(), v.end()
vector<int>canBeChildren[5005];
vector<int>adj[5005];
vector<int>adj_rev[5005];
vector<bool>vis(5005);
ll salary[5005];
vector<int>topo;
void dfs(int node){
for(int possibleChild : canBeChildren[node]){
if(!vis[possibleChild]){
vis[possibleChild] = 1;
adj[node].push_back(possibleChild);
adj_rev[possibleChild].push_back(node);
dfs(possibleChild);
}
}
topo.push_back(node);
}
void dfs_rev(int node){
salary[node] += 1;
for(int parent : adj_rev[node]){
salary[parent] += salary[node];
}
}
int main()
{
ACPLS("");
int n;
cin>>n;
for(int i = 1; i <= n; i++){
int k;
cin>>k;
for(int j = 0; j < k; j++){
int parent;
cin>>parent;
canBeChildren[parent].push_back(i);
}
}
ll ans = 4e18;
int root = -1;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= 5000; j++){
adj[j].clear();
adj_rev[j].clear();
vis[j] = 0;
salary[j] = 0;
}
topo.clear();
vis[i] = 1;
dfs(i);
bool ok = 1;
for(int j = 1; j <= n; j++){
if(!vis[j]){
ok = 0;
break;
}
}
if(!ok)continue;
for(int node : topo){
dfs_rev(node);
}
ll res = 0;
for(int j = 1; j <= n; j++){
res+=salary[j];
}
if(res<ans){
ans = res;
root = i;
}
}
cout<<ans;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |