oj.uz

Submission #582424

# Submission time Handle Problem Language Result Execution time Memory
582424 2022-06-23T18:17:19 Z ljuba Bosses (BOI16_bosses) C++17
100 / 100
 974 ms 720 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
 
typedef vector<int> vi;
typedef vector<ll> vll;
 
typedef vector<vi> vvi;
typedef vector<vll> vvll;
 
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
typedef vector<pii> vpii;
typedef vector<pll> vpll;
 
typedef vector<vpii> vvpii;
typedef vector<vpll> vvpll;
 
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define fi first
#define se second
 
template<class T> bool ckmin(T &a, const T &b) {return a > b ? a = b, 1 : 0;}
template<class T> bool ckmax(T &a, const T &b) {return a < b ? a = b, 1 : 0;}
 
namespace debug {
    void __print(int x) {cerr << x;}
    void __print(long long x) {cerr << x;}
    void __print(double x) {cerr << x;}
    void __print(long double x) {cerr << x;}
    void __print(char x) {cerr << '\'' << x << '\'';}
    void __print(const string &x) {cerr << '\"' << x << '\"';}
    void __print(const char *x) {cerr << '\"' << x << '\"';}
    void __print(bool x) {cerr << (x ? "true" : "false");}
 
    template<typename T, typename V>
    void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
    template<typename T>
    void __print(const T &x) {int f = 0; cerr << '{'; for(auto z : x) cerr << (f++ ? "," : ""), __print(z); cerr << "}";}
    void _print() {cerr << "]\n";}
    template <typename T, typename... V>
    void _print(T t, V... v) {__print(t); if(sizeof...(v)) cerr << ", "; _print(v...);}
 
#ifdef ljuba
#define dbg(x...) cerr << "\e[91m" << "LINE(" << __LINE__ << ") -> " << "[" << #x << "] = ["; _print(x)
#else
#define dbg(x...)
#endif
}
 
using namespace debug;
 
const char nl = '\n';
 
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
 
/*
“If you win, you live. If you lose, you die. If you don’t fight, you can’t win!”
― Eren Yaeger
*/

const int mxN = 6005;

vi adj[mxN];

const int INF = 1e9 + 12;

void solve() {
    int n;
    cin >> n;
    for(int i = 0; i < n; ++i) {
        int k;
        cin >> k;
        for(int j = 0; j < k; ++j) {
            int x;
            cin >> x;
            --x;
            adj[x].pb(i);
        }
    }

    auto resi = [&](int s) {
        vector<bool> vis(n, false);
        vi dist(n, INF);
        queue<int> q;

        q.push(s);
        dist[s] = 1;

        while(!q.empty()) {
            auto tren = q.front();
            q.pop();
            if(vis[tren]) continue;
            vis[tren] = true;

            for(auto e : adj[tren]) {
                if(!vis[e]) {
                    q.push(e);
                    ckmin(dist[e], dist[tren] + 1);
                }
            }
        }

        for(int i = 0; i < n; ++i) {
            if(!vis[i]) return INF;
        }

        int ans = 0;
        for(int i = 0; i < n; ++i) {
            ans += dist[i];
        }

        return ans;
    };

    int ans = INF;

    for(int i = 0; i < n; ++i) {
        ckmin(ans, resi(i));
    }

    cout << ans << nl;
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int testCases = 1;
    //cin >> testCases;
    while(testCases--)
        solve();
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 392 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 464 KB Output is correct

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 392 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 464 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 15 ms 468 KB Output is correct
13 Correct 12 ms 596 KB Output is correct
14 Correct 142 ms 588 KB Output is correct
15 Correct 13 ms 612 KB Output is correct
16 Correct 619 ms 672 KB Output is correct
17 Correct 974 ms 596 KB Output is correct
18 Correct 953 ms 720 KB Output is correct