oj.uz

Submission #74004

# Submission time Handle Problem Language Result Execution time Memory
74004 2018-08-29T15:26:03 Z claudy Bosses (BOI16_bosses) C++14
100 / 100
 965 ms 4876 KB 
# pragma GCC optimize("O3")
# include <bits/stdc++.h>
std::pair<int,int> DR[] = {{-1,0},{0,1},{1,0},{0,-1},{-1,1},{-1,-1},{1,1},{1,-1}};
# define ll long long
# define clock (clock() * 1000.0 / CLOCKS_PER_SEC)
# define rc(s) return cout << s,0
# define rcg(s) cout << s;exit(0)
# define _ ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
# define db(x) cerr << #x << " = " << x << '\n'
# define pb push_back
# define mp make_pair
# define all(s) s.begin(),s.end()
# define sz(x) (int)((x).size())
//# define int ll
using namespace std;

int n,k,x;
vector<int>vec[1 << 17];
int viz[1 << 17];

int f(int nod)
{
    queue<pair<int,int>>q;
    memset(viz,0,sizeof(viz));
    q.push(mp(nod,1));
    int cnt = 0;
    int x = 0;
    while(!q.empty())
    {
        int v = q.front().first;
        int cst = q.front().second;
        q.pop();
        if(viz[v]) continue;
        viz[v] = 1;
        x += cst;
        cnt++;
        for(auto it : vec[v])
        {
            if(!viz[it]){
                q.push(mp(it,cst + 1));
            }    
        }
    }
    if(cnt == n)
    return x;
    else return 1e9;
}

int32_t main(){_
    //freopen("input","r",stdin);
    cin >> n;
    for(int i = 1;i <= n;i++)
    {
        cin >> k;
        while(k--)
        {
            cin >> x;
            vec[x].pb(i);
        }
    }
    int ans = 1e9;
    for(int i = 1;i <= n;i++)
    {
        ans = min(ans,f(i));
    }
    rc(ans);
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3960 KB Output is correct
2 Correct 6 ms 3960 KB Output is correct
3 Correct 6 ms 4012 KB Output is correct
4 Correct 8 ms 4012 KB Output is correct
5 Correct 9 ms 4068 KB Output is correct
6 Correct 8 ms 4072 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3960 KB Output is correct
2 Correct 6 ms 3960 KB Output is correct
3 Correct 6 ms 4012 KB Output is correct
4 Correct 8 ms 4012 KB Output is correct
5 Correct 9 ms 4068 KB Output is correct
6 Correct 8 ms 4072 KB Output is correct
7 Correct 13 ms 4332 KB Output is correct
8 Correct 8 ms 4476 KB Output is correct
9 Correct 8 ms 4476 KB Output is correct
10 Correct 10 ms 4476 KB Output is correct
11 Correct 11 ms 4476 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3960 KB Output is correct
2 Correct 6 ms 3960 KB Output is correct
3 Correct 6 ms 4012 KB Output is correct
4 Correct 8 ms 4012 KB Output is correct
5 Correct 9 ms 4068 KB Output is correct
6 Correct 8 ms 4072 KB Output is correct
7 Correct 13 ms 4332 KB Output is correct
8 Correct 8 ms 4476 KB Output is correct
9 Correct 8 ms 4476 KB Output is correct
10 Correct 10 ms 4476 KB Output is correct
11 Correct 11 ms 4476 KB Output is correct
12 Correct 32 ms 4480 KB Output is correct
13 Correct 27 ms 4496 KB Output is correct
14 Correct 302 ms 4548 KB Output is correct
15 Correct 148 ms 4620 KB Output is correct
16 Correct 963 ms 4764 KB Output is correct
17 Correct 965 ms 4824 KB Output is correct
18 Correct 965 ms 4876 KB Output is correct