oj.uz

Submission #851042

# Submission time Handle Problem Language Result Execution time Memory
851042 2023-09-18T11:08:16 Z emkow Bosses (BOI16_bosses) C++17
67 / 100
 1500 ms 1468 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
#define pb emplace_back
#define ins insert
#define ssize(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pii pair <int, int>
#define pll pair <ll, ll>
#define pld pair <ld, ld>
#define st first
#define nd second

using namespace std;
using ll = int_fast64_t;
// using lll = __int128_t;
using ld = long double;
const int oo = 1e9 + 7;
const int mod = 1e9 + 7;

void solve(){
    int n; cin >> n;
    vector <vector<int>> pos(n);
    for(int i = 0; i < n; i ++){
        int k; cin >> k;
        while(k --){
            int x; cin >> x;
            -- x;
            pos[x].pb(i);
        }
    }
    auto calc = [&](int x){
        vector <vector<int>> g(n);
        vector <bool> vis(n, 0);
        queue <int> q;
        q.emplace(x);
        vis[x] = 1;
        int cnt = 0;
        while(ssize(q)){
            int v = q.front();
            q.pop();
            ++ cnt;
            for(auto u: pos[v]){
                if(!vis[u]){
                    vis[u] = 1;
                    g[v].pb(u);
                    g[u].pb(v);
                    q.emplace(u);
                }
            }
        }
        if(cnt != n) return oo;
        vector <int> dp(n, 0);
        function<void(int, int)> dfs = [&](int v, int p){
            for(auto u: g[v]){
                if(u == p) continue;
                dfs(u, v);
                dp[v] += dp[u];
            }
            dp[v] ++;
        };
        dfs(x, -1);
        return accumulate(all(dp), 0);
    };
    int ans = oo;
    for(int i = 0; i < n; i ++){
        ans = min(ans, calc(i));
    }
    cout << ans << '\n';
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t; t = 1;
    // cin >> t;
    while(t --) solve();
    return 0;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 2 ms 348 KB Output is correct
12 Correct 7 ms 344 KB Output is correct
13 Correct 5 ms 588 KB Output is correct
14 Correct 637 ms 1468 KB Output is correct
15 Correct 33 ms 844 KB Output is correct
16 Execution timed out 1554 ms 1024 KB Time limit exceeded
17 Halted 0 ms 0 KB -