oj.uz

Submission #264284

# Submission time Handle Problem Language Result Execution time Memory
264284 2020-08-14T06:00:47 Z Fidisk Bosses (BOI16_bosses) C++14
100 / 100
 896 ms 848 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define oo 1e9
#define fi first
#define se second
#define sp(iiii) setprecision(iiii)
#define IO ios_base::sync_with_stdio(false); cin.tie(0)
#define ms(aaaa,xxxx) memset(aaaa,xxxx,sizeof(aaaa))
#define cntbit(xxxx) __builtin_popcount(xxxx)
#define getbit(xxxx,aaaa) ((xxxx>>(aaaa-1))&1)
#define _cos(xxxx) cos(xxxx*acos(-1)/180)
#define _sin(xxxx) sin(xxxx*acos(-1)/180)
#define _tan(xxxx) tan(xxxx*acos(-1)/180)
#define PE cout<<fixed
 
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<pair<int,int>,int> piii;
typedef pair<long long,long long> pll;
typedef pair<pair<long long,long long>,long long> plll;
 
const ld pi=acos(-1);

queue<pll> q;
int res,n,i,k,j,v;
bool ok[5009];
vector<ll> g[5009];

int solve(ll x) {
    q.push({x,2});
    for (int ii=1;ii<=n;ii++) {
        ok[ii]=false;
    }
    ok[x]=true;
    int kq=1;
    int sl=1;
    while (!q.empty()) {
        pll tmp=q.front();
        q.pop();
        for (int ii=0;ii<g[tmp.fi].size();ii++) {
            if (!ok[g[tmp.fi][ii]]) {
                kq+=tmp.se;
                q.push({g[tmp.fi][ii],tmp.se+1});
                ok[g[tmp.fi][ii]]=true;
                sl++;
            }
        }
    }
    if (sl<n) {
        return oo;
    }
    return kq;
}

int main(){
    IO;
    cin>>n;
    for (i=1;i<=n;i++) {
        cin>>k;
        for (j=1;j<=k;j++) {
            cin>>v;
            g[v].push_back(i);
        }
    }
    res=oo;
    for (i=1;i<=n;i++) {
        res=min(res,solve(i));
    }
    cout<<res<<'\n';
}

Compilation message

bosses.cpp: In function 'int solve(ll)':
bosses.cpp:43:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         for (int ii=0;ii<g[tmp.fi].size();ii++) {
      |                       ~~^~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 7 ms 640 KB Output is correct
13 Correct 4 ms 640 KB Output is correct
14 Correct 240 ms 632 KB Output is correct
15 Correct 32 ms 640 KB Output is correct
16 Correct 822 ms 756 KB Output is correct
17 Correct 896 ms 640 KB Output is correct
18 Correct 895 ms 848 KB Output is correct