oj.uz

Submission #77148

# Submission time Handle Problem Language Result Execution time Memory
77148 2018-09-23T04:36:40 Z Mercenary Bosses (BOI16_bosses) C++11
100 / 100
 542 ms 1432 KB 
#include<bits/stdc++.h>

using namespace std;
#define taskname ""
#define pb	push_back
typedef long double ld;
typedef long long ll;
const int maxn = 5e3 + 5;
int n , deq[maxn] , sz , chk[maxn];
int res = (ll)1e9;
vector<int> v[maxn];
int sum = 0;
void BFS(int u)
{
    fill_n(chk , maxn , 0);
    deq[0] = u;
    sz = 1;
    chk[u] = 1;
    int edgecount = 0;
    sum = 1;
    int it = 0;
    while(sz > it)
    {
        int from = deq[it];
        ++it;
        for(int c : v[from])
            if(chk[c] == 0)
            {
                chk[c] = chk[from] + 1;
                sum += chk[c];
                deq[sz++] = c;
                edgecount++;
            }
    }
    if(edgecount == n - 1){
        res = min(res , sum);
    }
}
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	//freopen(taskname".INP", "r",stdin);
	//freopen(taskname".OUT", "w",stdout);
    cin >> n;
    for(int i = 1 ; i <= n ; ++i)
    {
        int k;cin >> k;
        while(k--)
        {
            int x;cin >> x;
            v[x].pb(i);
        }
    }
    for(int i = 1 ; i <= n ; ++i)BFS(i);
    cout << res;
}
/*
    4
    1 4
    3 1 3 4
    2 1 2
    1 3
*/

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 576 KB Output is correct
4 Correct 2 ms 720 KB Output is correct
5 Correct 2 ms 720 KB Output is correct
6 Correct 2 ms 760 KB Output is correct

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 576 KB Output is correct
4 Correct 2 ms 720 KB Output is correct
5 Correct 2 ms 720 KB Output is correct
6 Correct 2 ms 760 KB Output is correct
7 Correct 2 ms 760 KB Output is correct
8 Correct 3 ms 876 KB Output is correct
9 Correct 2 ms 876 KB Output is correct
10 Correct 3 ms 876 KB Output is correct
11 Correct 3 ms 876 KB Output is correct
12 Correct 8 ms 892 KB Output is correct
13 Correct 6 ms 960 KB Output is correct
14 Correct 129 ms 1000 KB Output is correct
15 Correct 16 ms 1016 KB Output is correct
16 Correct 537 ms 1156 KB Output is correct
17 Correct 542 ms 1240 KB Output is correct
18 Correct 536 ms 1432 KB Output is correct