# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
107343 | MohamedAhmed0 | Bosses (BOI16_bosses) | C++14 | 1552 ms | 768 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int MAX = 5005 ;
int vis[MAX] , par[MAX];
long long dp[MAX] , cost = 0;
vector< vector<int> >adj(MAX) ;
int n , cnt = 0 ;
void bfs(int src)
{
queue<int>q ;
q.push(src) ;
vis[src] = 1 ;
par[src] = 0 ;
while(!q.empty())
{
int node = q.front() ;
q.pop() ;
cnt++ ;
for(auto &child : adj[node])
{
if(vis[child] == 1)
continue ;
vis[child] = 1 ;
par[child] = node ;
q.push(child) ;
}
}
return ;
}
void dfs(int node)
{
for(auto &child : adj[node])
{
if(par[child] == node)
{
dfs(child) ;
dp[node] += dp[child] ;
}
}
dp[node]++;
cost += dp[node] * 1ll;
return ;
}
int main()
{
scanf("%d" , &n) ;
for(int i = 1 ; i <= n ; ++i)
{
int m ;
scanf("%d" , &m) ;
while(m--)
{
int x ;
scanf("%d" , &x) ;
adj[x].push_back(i) ;
}
}
long long ans = 1e18 ;
for(int i = 1 ; i <= n ; ++i)
{
memset(vis , 0 , sizeof(vis)) ;
memset(dp , 0 , sizeof(dp)) ;
memset(par , 0 , sizeof(par)) ;
cnt = 0 , cost = 0;
bfs(i) ;
if(cnt != n)
continue;
dfs(i) ;
ans = min(ans , cost) ;
}
return printf("%lld" , ans) , 0 ;
}
컴파일 시 표준 에러 (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... |