Submission #975557

#	Time	Username	Problem	Language	Result	Execution time	Memory
975557		dong_gas	Bosses (BOI16_bosses)	C++17	67 / 100	1539 ms	9668 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=1e18;
queue<int> v[5050], hubo[5050];
vector<int> adj[5050];
int a[5050];

void dfs(int u) {
    a[u]=1;
    for(int& v:adj[u]) {
        dfs(v);
        a[u]+=a[v];
    }
}

int f(int r) {
    for(int i=1;i<=n;i++) adj[i].clear(), hubo[i]=v[i], a[i]=0;
    vector<bool> visited(n+1,0);
    queue<int> q;
    q.push(r);
    visited[r]=1;
    while(!q.empty()) {
        int u=q.front(); q.pop();
        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);
        }
    }
    int cnt=0;
    for(int i=1;i<=n;i++) if(visited[i]) cnt++;
    if(cnt<n) return 1e18;
    dfs(r);
    return accumulate(a+1,a+n+1,0);
}

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();
}

Compilation message (stderr)

bosses.cpp:8:12: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
    8 | int n, ans=1e18;
      |            ^~~~
bosses.cpp: In function 'int f(int)':
bosses.cpp:39:22: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   39 |     if(cnt<n) return 1e18;
      |                      ^~~~

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