Submission #901352

#	Time	Username	Problem	Language	Result	Execution time	Memory
901352		Blagoj	Bosses (BOI16_bosses)	C++17	100 / 100	450 ms	1112 KiB

bosses

#include <bits/stdc++.h>
 
#pragma GCC optimize("Ofast,unroll-loops")
 
using namespace std;
 
#define endl '\n'
#define ll long long
#define all(x) x.begin(), x.end()
 
struct T {
    int depth, place;
};
 
bool operator < (T a, T b) {
    return a.depth < b.depth;
}
 
priority_queue<T> pq;
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    vector<int> g[n + 2];
    for (int i = 1; i <= n; i++) {
        int sz; cin >> sz;
        for (int j = 0; j < sz; j++) {
            int t; cin >> t;
            g[t].push_back(i);
        }
    }
    ll ans = LLONG_MAX, mnDepth = LLONG_MAX;
    for (int boss = 1; boss <= n; boss++) {
        queue<int> q;
        bool visited[n + 2];
        int to[n + 2], depth[n + 2];
        memset(depth, 0, sizeof(depth));
        vector<int> leaf;
        memset(visited, 0, sizeof(visited));
        q.push(boss);
        visited[boss] = 1;
        int cnt = 0, mxDepth = 0;
        while (q.size() > 0) {
            cnt++;
            int fr = q.front();
            q.pop();
            mxDepth += depth[fr];
            bool next = 0;
            for (auto x : g[fr]) {
                if (visited[x]) continue;
                depth[x] = depth[fr] + 1;
                next = 1;
                to[x] = fr;
                visited[x] = 1;
                q.push(x);
            }
            if (!next) leaf.push_back(fr);
        }
        if (mxDepth > mnDepth) continue;
        if (cnt != n) continue;
        int vals[n + 2];
        memset(vals, 0, sizeof(vals));
        for (auto x : leaf) {
            pq.push({depth[x], x});
            vals[x] = 1;
        }
        while (pq.size() > 0) {
            int top = pq.top().place;
            pq.pop();
            if (vals[to[top]] == 0) vals[to[top]] = vals[top] + 1;
            else vals[to[top]] += vals[top];
            if (to[top] != boss && vals[to[top]] == vals[top] + 1) pq.push({depth[to[top]], to[top]});
        }
        cout << endl;
        ll sum = 0;
        for (int i = 1; i <= n; i++) {
            sum += vals[i];
            // cout << i << " : " << vals[i] << "\n";
        }
        // cout << boss << " " << sum << endl;
        mnDepth = mxDepth;
        ans = min(ans, sum);
    }
    cout << ans;
}

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