oj.uz

Submission #350794

# Submission time Handle Problem Language Result Execution time Memory
350794 2021-01-19T08:26:54 Z Hossein8320 Bosses (BOI16_bosses) C++17
100 / 100
 885 ms 1028 KB 
// That's what she said !
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
const int maxn = 5e3 + 9 , modn = 1e9 + 7;
int n, v, k, ans = 1e18, cnt[maxn], h[maxn];
bool mark[maxn];
vector <int> adj[maxn], adj2[maxn];
int bfs(int v)
{
    queue <int> q;
    int H = 0, sum = 0, g = 0;
    mark[v] = 1;
    cnt[0] = 1;
    q.push(v);
    while(q.size()){
        v = q.front();
        q.pop();
        for(auto i : adj[v]){
            if(mark[i])
                continue;
            h[i] = h[v] + 1;
            cnt[h[i]]++;
            H = max(H , h[i]);
            mark[i] = 1;
            q.push(i);
        }
    }
    for(int i = H; i > -1; i--){
        g += cnt[i];
        sum += g;
    }
    for(int i = 1; i <= n; i++)
        if(!mark[i])
            return -1;
    return sum;
}
int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n;
	for(int i = 1; i <= n; i++){
        cin >> k;
        for(int j = 0; j < k; j++){
            cin >> v;
            adj[v].push_back(i);
        }
	}
    for(int i = 1; i <= n; i++){
        int p = bfs(i);
        if(p != -1)
            ans = min(ans , p);
        for(int i = 0; i <= n; i++){
            cnt[i] = h[i] = 0;
            mark[i] = 0;
        }
    }
    cout << ans;
	return 0;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 1 ms 620 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 1 ms 620 KB Output is correct
7 Correct 1 ms 620 KB Output is correct
8 Correct 1 ms 620 KB Output is correct
9 Correct 1 ms 620 KB Output is correct
10 Correct 1 ms 620 KB Output is correct
11 Correct 1 ms 620 KB Output is correct
12 Correct 5 ms 748 KB Output is correct
13 Correct 4 ms 748 KB Output is correct
14 Correct 202 ms 844 KB Output is correct
15 Correct 54 ms 748 KB Output is correct
16 Correct 688 ms 1028 KB Output is correct
17 Correct 862 ms 940 KB Output is correct
18 Correct 885 ms 1004 KB Output is correct