oj.uz

Submission #857986

# Submission time Handle Problem Language Result Execution time Memory
857986 2023-10-07T08:50:13 Z vjudge1 Bosses (BOI16_bosses) C++17
67 / 100
 1500 ms 984 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long int
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
const int maxn = 5e3 + 5, maxk = 1e4 + 5;

bool mark[maxn];
int H_cnt[maxn], n;
vector<pii > P_pars;

int calc(int root) {
    vector<int> height[maxn];
    memset(H_cnt, 0, sizeof H_cnt);
    memset(mark, false, sizeof mark);
    height[0].pb(root);
    H_cnt[0] = 1;
    mark[root] = true;
    ll sum = n, dec = 1;
    for (int i = 1; i < n; i++) {
        for (int x: height[i - 1]) {
            for (pii u: P_pars) {
                int v = u.first, par = u.second;
                if (par == x and v != x and !mark[v]) {
                    height[i].pb(v);
                    H_cnt[i]++;
                    mark[v] = true;
                }
            }
        }
        sum += n - dec;
        dec += H_cnt[i];
    }
    return sum;
}

inline int minn(ll a, ll b) {
    if(a <= b)
        return a;
    else
        return b;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int mx = 0;
    vector<int> roots;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int c;
        cin >> c;
        for (int j = 1; j <= c; j++) {
            int x;
            cin >> x;
            P_pars.pb({i, x});
        }
    }
    ll ans = 1e18;
    for (int i = 1; i <= n; i++) {
        ans = minn(ans, calc(i));
    }
    cout << ans;
    return 0;
}

Compilation message

bosses.cpp: In function 'int main()':
bosses.cpp:51:9: warning: unused variable 'mx' [-Wunused-variable]
   51 |     int mx = 0;
      |         ^~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 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 404 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 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 404 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 3 ms 460 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 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 404 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 3 ms 460 KB Output is correct
12 Correct 214 ms 856 KB Output is correct
13 Correct 145 ms 816 KB Output is correct
14 Execution timed out 1562 ms 984 KB Time limit exceeded
15 Halted 0 ms 0 KB -