제출 #1303409

#제출 시각아이디문제언어결과실행 시간메모리
1303409zbyszkoBosses (BOI16_bosses)C++20
67 / 100
1593 ms904 KiB
#include <bits/stdc++.h>
using namespace std;

using ull = unsigned long long;
using ll = long long;
#define x first
#define y second

vector<vector<int>> adj;

ll bdfs(int f,int n){
    vector<vector<int>> ch(n+1);
    vector<bool> visit(n+1,false);
    int used=0;
    queue<int> q;
    q.push(f);
    visit[f]=true;
    used++;
    int v;
    while(!q.empty()){
        v=q.front();
        q.pop();
        for(int c:adj[v]){
            if(!visit[c]){
                visit[c]=true;
                ch[v].push_back(c);
                used++;
                q.push(c);
            }
        }
    }
    if(used<n){
        return LLONG_MAX;
    }
    vector<int> dp(n+1,0);
    ll sum=0;
    stack<tuple<int,int,bool>> s;
    s.push({f,-1,0});
    visit[f]=true;
    while(!s.empty()){
        auto [v,p,st]=s.top();
        s.pop();
        if(st==0){
            s.push({v,p,1});
            for(int c:ch[v]){
                if(c==p) continue;
                s.push({c,v,0});
            }
        }
        else{
            dp[v]=1;
            for(int c:ch[v]){
                if(c!=p){
                    dp[v]+=dp[c];
                }
            }
            sum+=dp[v];
        }
    }
    return sum;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n;cin >> n;
    adj.resize(n+1);
    for(int i=1,k;i<=n;i++){
        cin >> k;
        for(int j=0,v;j<k;j++){
            cin >> v;
            adj[v].push_back(i);
        }
    }
    ll sum=LLONG_MAX;
    for(int i=1;i<=n;i++){
        if(adj[i].size()>1) sum=min(sum,bdfs(i,n));
    } 
    if(sum==LLONG_MAX){
        for(int i=1;i<=n;i++){
            if(adj[i].size()>0) sum=min(sum,bdfs(i,n));
        }
    }
    cout << sum;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...