제출 #1366167

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1366167		ivaziva	Bosses (BOI16_bosses)	C++20	100 / 100	655 ms	1180 KiB

bosses

#include <bits/stdc++.h>
#include <cstdint>

using namespace std;

#define MAXN 5005
#define int long long

int n;
vector<int> boss[MAXN];
int deg[MAXN],dist[MAXN];
vector<int> adj[MAXN];
queue<int> nodes;

void dfs(int node,int pret,int depth)
{
    dist[node]=depth;
    for (int sled:adj[node])
    {
        if (sled!=pret) dfs(sled,node,depth+1);
    }
}

int32_t main()
{
    cin>>n;
    for (int node=1;node<=n;node++)
    {
        int siz;cin>>siz;for (int num=1;num<=siz;num++) {int sled;cin>>sled;boss[sled].push_back(node);}
    }
    int answer=LLONG_MAX;
    for (int root=1;root<=n;root++)
    {
        for (int node=1;node<=n;node++) {deg[node]=0;dist[node]=0;adj[node].clear();}
        nodes.push(root);
        while (!nodes.empty())
        {
            int node=nodes.front();nodes.pop();
            for (int sled:boss[node])
            {
                if (deg[sled]!=0) continue;
                deg[node]++;deg[sled]++;nodes.push(sled);
                adj[node].push_back(sled);adj[sled].push_back(node);
            }
        }
        bool valid=true;
        for (int node=1;node<=n;node++)
        {
            if (deg[node]==0) {valid=false;break;}
        }
        if (!valid) continue;
        dfs(root,0,0);int solution=n;
        for (int node=1;node<=n;node++) solution+=dist[node];
        answer=min(answer,solution);
    }
    cout<<answer<<endl;
}

• 서브태스크 1: 22 / 22
• 서브태스크 2: 45 / 45
• 서브태스크 3: 33 / 33