oj.uz

Submission #525210

# Submission time Handle Problem Language Result Execution time Memory
525210 2022-02-11T05:09:22 Z AA_Surely Bosses (BOI16_bosses) C++17
100 / 100
 1376 ms 980 KB 
#include <bits/stdc++.h>

#define FOR(i,x,n) 	for(int i=x; i<n; i++)
#define F0R(i,n) 	FOR(i,0,n)
#define ROF(i,x,n) 	for(int i=n-1; i>=x; i--)
#define R0F(i,n) 	ROF(i,0,n)

#define WTF 		cout << "WTF" << endl

#define IOS 		ios::sync_with_stdio(false); cin.tie(0)
#define F 			first
#define S	 		second
#define pb 			push_back

#define ALL(x) 		x.begin(), x.end()
#define RALL(x) 	x.rbegin(), x.rend()

using namespace std;
typedef long long 		LL;

typedef pair<int, int> 	PII;
typedef pair<LL, LL> 	PLL;

typedef vector<int> 	VI;
typedef vector<LL> 		VLL;
typedef vector<PII> 	VPII;
typedef vector<PLL> 	VPLL;

const int MAXN = 5000 + 7;
const int ALPHA = 27;
const LL INF = 1e17 + 7;
const int MOD = 1e9 + 7;
const int LOG = 22;

int n, m;
LL dist[MAXN];
VI adj[MAXN], ndj[MAXN];
int dp[MAXN];

LL dfs(int now) {
    dp[now] = 1;
    for(int on : ndj[now])
        dp[now] += dfs(on);
    return dp[now];
}


LL bfs(int sc) {
    fill(dist, dist + n, INF);
    F0R(i, n) ndj[i].clear();

    dist[sc] = 0;

    queue<int> keep;
    keep.push(sc);

    while(!keep.empty()) {
        int now = keep.front();
        keep.pop();

        for(int on : adj[now]) {
            if (dist[on] > dist[now] + 1) {
                dist[on] = dist[now] + 1;
                keep.push(on);
                ndj[now].pb(on);
            }
        }
    }

    dfs(sc);
    LL sum = 0;
    F0R(i, n) sum += dp[i];
    LL mx = 0;
    F0R(i, n) mx = max(mx, dist[i]);
    return (mx == INF ? INF : sum);
}

int main() {
    IOS;
    cin >> n;

    int v;
    F0R(i, n) {
        int k; cin >> k;
        F0R(j, k) {
            cin >> v;
            adj[--v].pb(i);
        }
    }
    
    LL ans = INF;
    F0R(i, n) 
        ans = min(ans, bfs(i));
    cout << ans;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 556 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 5 ms 716 KB Output is correct
13 Correct 4 ms 612 KB Output is correct
14 Correct 352 ms 904 KB Output is correct
15 Correct 75 ms 788 KB Output is correct
16 Correct 1099 ms 928 KB Output is correct
17 Correct 1376 ms 976 KB Output is correct
18 Correct 1329 ms 980 KB Output is correct