oj.uz

Submission #975576

# Submission time Handle Problem Language Result Execution time Memory
975576 2024-05-05T13:36:33 Z dong_gas Bosses (BOI16_bosses) C++17
100 / 100
 851 ms 1104 KB 
#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;
vector<int> 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(), 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();
        for(int& v:hubo[u]) {
            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;
            hubo[x].emplace_back(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

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:38:22: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   38 |     if(cnt<n) return 1e18;
      |                      ^~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 0 ms 600 KB Output is correct
6 Correct 0 ms 604 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 0 ms 600 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 0 ms 600 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 4 ms 604 KB Output is correct
13 Correct 3 ms 828 KB Output is correct
14 Correct 146 ms 968 KB Output is correct
15 Correct 39 ms 860 KB Output is correct
16 Correct 539 ms 1104 KB Output is correct
17 Correct 851 ms 1024 KB Output is correct
18 Correct 838 ms 1020 KB Output is correct