Submission #975571

#	Time	Username	Problem	Language	Result	Execution time	Memory
975571		dong_gas	Bosses (BOI16_bosses)	C++17	67 / 100	1535 ms	9576 KiB

bosses

#include <bits/extc++.h>
#define all(v) v.begin(), v.end()
#define zip(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
 
int n, ans=1e9, p, R;
queue<int> v[5050], hubo[5050];
vector<int> adj[5050];

int dfs(int u) {
    int ret=1;
    for(int& v:adj[u]) ret+=dfs(v);
    //cout<<u<<' '<<ret<<endl;
    if(u!=R) p+=ret;
    return ret;
}

int f(int r) {
    R=r;
    for(int i=1;i<=n;i++) adj[i].clear(), hubo[i]=v[i];
    vector<bool> visited(n+1,0);
    queue<int> q;
    q.push(r);
    visited[r]=1;
    int cnt=0;
    p=0;
    while(!q.empty()) {
        int u=q.front(); q.pop();
        cnt++;
        while(!hubo[u].empty()) {
            int v=hubo[u].front(); hubo[u].pop();
            if(visited[v]) continue;
            visited[v]=1;            
            adj[u].push_back(v);
            q.push(v);
        }
    }    
    //cout<<cnt<<endl;
    if(cnt<n) return 1e9;
    return dfs(r)+p;
}

void solve() {
    cin>>n;
    for(int i=1;i<=n;i++) {
        int k; cin>>k;
        while(k --> 0) {
            ll x; cin>>x;
            v[x].push(i);
        }
    }
    for(int r=1;r<=n;r++) {
        ans=min(ans,f(r));
        //cout<<f(r)<<endl;
    }
    cout<<ans;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int tc=1; //cin>>tc;
    while(tc --> 0) solve();
}

• Subtask 1: 22 / 22
• Subtask 2: 45 / 45
• Subtask 3: 0 / 33