oj.uz

Submission #171758

# Submission time Handle Problem Language Result Execution time Memory
171758 2019-12-30T10:22:22 Z 0gnjen Bosses (BOI16_bosses) C++14
67 / 100
 1500 ms 764 KB 
//Failure will never overtake me if my determination to succeed is strong enough
#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;
    vector<int> a[n];

    for(int i = 0; i < n; i++)
    {
        int m;
        cin >> m;
        while(m--)
        {
            int x;
            cin >> x;
            a[x-1].push_back(i);
        }
    }

    long long rez = INT_MAX;
    for(int i = 0; i < n; i++)
    {
        int vis[n];
        for(int j = 0; j < n; j++)
            vis[j] = -1;

        queue<int> q;

        q.push(i);
        vis[i] = 1;

        while(!q.empty())
        {
            int x = q.front();
            q.pop();
            for(auto j: a[x])
            {
                if(vis[j] == -1)
                {
                    vis[j] = vis[x]+1;
                    q.push(j);
                }
            }
        }

        bool moze = true;
        map<int, int> nivoi;

        for(int j = 0; j < n; j++)
        {
            if(vis[j] == -1)
                moze = false;
            nivoi[vis[j]]++;
        }

        if(!moze)
            continue;

        long long tmpr = 0;
        for(auto j: nivoi)
        {
            tmpr += j.first*j.second;
        }

        rez = min(rez, tmpr);
    }

    cout << rez;

}

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 380 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 7 ms 504 KB Output is correct
13 Correct 6 ms 504 KB Output is correct
14 Correct 1245 ms 764 KB Output is correct
15 Correct 92 ms 672 KB Output is correct
16 Correct 1100 ms 752 KB Output is correct
17 Execution timed out 1570 ms 652 KB Time limit exceeded
18 Halted 0 ms 0 KB -