이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define ii pair<ll,ll>
const ll maxn=2e5+2;
int n;
vector<int> adj[maxn];
vector<int> g[4000];
int dp[4000];
int ans=INT_MAX;
int sum,cnt;
void dfs(int u){
//cout<<u<<endl;
dp[u]=1;
++cnt;
for (int v: g[u]){
dfs(v);
dp[u]+=dp[v];
}
sum+=dp[u];
}
void bfs(int s){
bool ok[n+3]={};
queue<int> q;
q.push(s);
ok[s]=1;
for (int i=1;i<=n;++i) g[i].clear();
while (!q.empty()){
int u=q.front();
q.pop();
for (int v: adj[u]){
if (!ok[v]){
ok[v]=1;
q.push(v);
g[u].push_back(v);
}
}
}
sum=cnt=0;
/*for (int i=1;i<=n;++i){
for (int j: g[i]) cout<<j<<" "; cout<<endl;
}*/
dfs(s);
//cout<<endl;
//cout<<s<<" "<<sum<<endl;
if (cnt==n) ans=min(ans,sum);
}
int main(){
cin>>n;
for (int i=1;i<=n;++i){
int k; cin>>k;
while (k--){
int x; cin>>x;
adj[x].push_back(i);
//cout<<x<<" "<<i<<endl;
}
}
//bfs(1);
//cout<<endl;
for (int i=1;i<=n;++i) bfs(i);
cout<<ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |