oj.uz

Submission #91786

# Submission time Handle Problem Language Result Execution time Memory
91786 2018-12-30T02:51:23 Z luckyboy Bosses (BOI16_bosses) C++14
100 / 100
 448 ms 888 KB 
/**Lucky Boy**/
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define maxc 1000000007
#define maxn 5005
#define maxm 500005
#define pii pair <int,int>
#define Task "Bosses"
template <typename T> inline void read(T &x){char c;bool nega=0;while((!isdigit(c=getchar()))&&(c!='-'));if(c=='-'){nega=1;c=getchar();}x=c-48;while(isdigit(c=getchar())) x=x*10+c-48;if(nega) x=-x;}
template <typename T> inline void writep(T x){if(x>9) writep(x/10);putchar(x%10+48);}
template <typename T> inline void write(T x){if(x<0){putchar('-');x=-x;}writep(x);putchar(' ');}
template <typename T> inline void writeln(T x){write(x);putchar('\n');}
using namespace std;
int n,s[maxn],top,bot,h[maxn];
vector <int> a[maxn];
long long ans = 1ll*maxc*maxc;
void Try(int st)
{
    FOR(i,1,n) h[i] = 0;
    h[st] = 1;
    s[top = bot = 1] = st;
    while (bot <= top)
    {
        int u = s[bot++];
        for (int v : a[u])
            if (!h[v])
            {
                h[v] = h[u] + 1;
                s[++top] = v;
                //cout << u << ' ' << v << '\n';
            }
    }
    long long res = 0;
    FOR(i,1,n)
        if (!h[i]) return;
        else res += h[i];
    ans = min(ans,res);
}
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen(Task".inp", "r",stdin);
    //freopen(Task".out", "w",stdout);
    cin >> n;
    FOR(i,1,n)
    {
        int x,y;
        cin >> x;
        FOR(j,1,x)
        {
            cin >> y;
            a[y].pb(i);
        }
    }
    FOR(i,1,n) Try(i);
    //Try(6);
    cout << ans;
    return 0;
}

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 504 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 504 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 504 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 2 ms 632 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 504 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 2 ms 632 KB Output is correct
12 Correct 5 ms 508 KB Output is correct
13 Correct 4 ms 632 KB Output is correct
14 Correct 96 ms 652 KB Output is correct
15 Correct 15 ms 632 KB Output is correct
16 Correct 425 ms 760 KB Output is correct
17 Correct 441 ms 760 KB Output is correct
18 Correct 448 ms 888 KB Output is correct