oj.uz

Submission #146071

# Submission time Handle Problem Language Result Execution time Memory
146071 2019-08-21T20:49:18 Z mat_v Bosses (BOI16_bosses) C++14
67 / 100
 1500 ms 1016 KB 
#include <bits/stdc++.h>
#define mod 1000000007
#define pb push_back
#define mid(l, r) ((l)+(r))/2
#define len(a) (a).length()
#define sz(a) (a).size()
#define xx first
#define yy second
#define inf int(2e9)
#define ff(i, a, b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i, a, b) for(int (i) = (a); (i) >= (b); --(i))
#define maxn 5005

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

template<class T>
void print(const T niz[], const int siz)
{
    for(int i=0;i<siz;i++)
        cout << niz[i] << " ";
    cout << endl;
}

int n;
int cnt;
vector<int>ngraf[maxn];
vector<int>graf[maxn];
bool bio[maxn];
ll resela = 1e9;
ll res;
ll dfs(int x){
    ll sta = 1;
    for(auto c:ngraf[x])sta += dfs(c);
    res += sta;
    return sta;
}
void bfs(int src){
    cnt = 0;
    res = 0;
    ff(i,1,n){
        ngraf[i].clear();
        bio[i] = 0;
    }
    queue<int>q;
    q.push(src);
    while(!q.empty()){
        ++cnt;
        int tren = q.front();
        bio[tren] = 1;
        q.pop();
        for(auto c:graf[tren]){
            if(!bio[c]){
                bio[c] = 1;
                q.push(c);
                ngraf[tren].pb(c);
            }
        }
    }
    ll pom = 0;;
    if(cnt != n)return;
    pom  = dfs(src);
    resela = min(resela, res);
    //resela = min(resela,pom);
    //cout << src << " " << pom << endl;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin >> n;
    ff(i,1,n){
        int k;
        cin >> k;
        ff(j,1,k){
            int a;
            cin >> a;
            graf[a].pb(i);
        }
    }
    ff(i,1,n){
        bfs(i);

    }
    cout << resela;
    return 0;
}

Compilation message

bosses.cpp: In function 'void bfs(int)':
bosses.cpp:62:8: warning: variable 'pom' set but not used [-Wunused-but-set-variable]
     ll pom = 0;;
        ^~~

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 2 ms 632 KB Output is correct
3 Correct 2 ms 632 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 632 KB Output is correct
6 Correct 2 ms 636 KB Output is correct
7 Correct 2 ms 632 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 3 ms 632 KB Output is correct
11 Correct 3 ms 632 KB Output is correct
12 Correct 8 ms 760 KB Output is correct
13 Correct 6 ms 760 KB Output is correct
14 Correct 239 ms 860 KB Output is correct
15 Correct 36 ms 760 KB Output is correct
16 Correct 877 ms 888 KB Output is correct
17 Execution timed out 1552 ms 1016 KB Time limit exceeded
18 Halted 0 ms 0 KB -