이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define maxn 5005
using namespace std;
int n;
vector<int>d[maxn],adj[maxn];
bool bio[maxn];
queue<pair<int,int>>mq;
void bfs(int v)
{
mq.push({v,-1});
while(!mq.empty())
{
int u=mq.front().first;
int w=mq.front().second;
mq.pop();
if(bio[u])continue;
bio[u]=true;
if(w!=-1)adj[w].push_back(u);
for(auto x:d[u])
{
if(bio[x])continue;
mq.push({x,u});
}
}
}
int tre;
int dp[maxn];
void dfs(int v)
{
dp[v]=1;
for(auto x:adj[v])
{
dfs(x);
dp[v]+=dp[x];
}
//cout<<dp[v]<<" ";
tre+=dp[v];
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin>>n;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
for(int j=0;j<x;j++)
{
int w;
cin>>w;
d[w].push_back(i);
}
}
/*for(int i=1;i<=n;i++)
{
cout<<i<<" "<<d[i].size()<<" ";
for(auto x:d[i])cout<<x<<" ";
cout<<endl;
}
cout<<endl<<endl;*/
int sol=5*maxn*maxn;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
bio[j]=false;
adj[j].clear();
dp[j]=0;
}
tre=0;
bfs(i);
/*for(int j=1;j<=n;j++)
{
cout<<j<<" "<<adj[j].size()<<" ";
for(auto x:adj[j])cout<<x<<" ";
cout<<endl;
}*/
dfs(i);
//cout<<endl;for(int j=1;j<=n;j++)cout<<dp[j]<<" ";
sol=min(tre,sol);
/*cout<<tre<<endl;
cout<<endl<<endl;*/
}
cout<<sol<<endl;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |