oj.uz

Submission #341306

# Submission time Handle Problem Language Result Execution time Memory
341306 2020-12-29T11:49:33 Z AlexNeagu Bosses (BOI16_bosses) C++14
100 / 100
 1219 ms 876 KB 
#include<bits/stdc++.h>
// #define int long long
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pi;
const int mod = 1e9 + 9;
const int N = 106 * 106;
const int nax = 1e6+6;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n;
ll ans = 2e18;
vector<int> possible_childs[5005];

ll root(int x) {
    
    queue<int> Q;
    Q.push(x);
    vector<int> d(n + 1, 2e9), p(n + 1);
    vector<ll> cnt(n + 1, 1LL);
    vector<int> ord;
    d[x] = 0;

    while(Q.size()) {
        int node = Q.front();
        ord.pb(node);
        Q.pop();
        for(auto it : possible_childs[node]) {
            if(d[node] + 1 < d[it]) {
                d[it] = d[node] + 1;
                Q.push(it);
                p[it] = node;
            }
        }
    }

    for(int i = 1; i <= n; i++) if(d[i] == 2e9) return 2e18;
    reverse(ord.begin(), ord.end());
    ll sol = 0;
    
    for(auto it : ord) {
        sol += cnt[it];
        if(it != x) {
            cnt[p[it]] += cnt[it];
        }
    }
    return sol;
}

int32_t main() {
 
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for(int i = 1; i <= n; i++) {
        int len;
        cin >> len;
        for(int j = 1; j <= len; j++) {
            int x;
            cin >> x;
            possible_childs[x].push_back(i);
        }
    }

    for(int i = 1; i <= n; i++) {
        ans = min(ans, root(i));
    }

    cout << ans << '\n';


    return 0;
}

Compilation message

bosses.cpp:4: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("O3")
      | 
bosses.cpp:5: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 6 ms 492 KB Output is correct
13 Correct 6 ms 492 KB Output is correct
14 Correct 216 ms 748 KB Output is correct
15 Correct 42 ms 620 KB Output is correct
16 Correct 756 ms 876 KB Output is correct
17 Correct 1205 ms 876 KB Output is correct
18 Correct 1219 ms 876 KB Output is correct