oj.uz

Submission #79527

# Submission time Handle Problem Language Result Execution time Memory
79527 2018-10-15T01:49:27 Z Flying_dragon_02 Bosses (BOI16_bosses) C++14
100 / 100
 716 ms 1020 KB 
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;

int n;
long long ans = LLONG_MAX;
bool vis[5005];

vector<int> graph[5005];

queue<ii> pq;

long long lmao(int u) {
    memset(vis, 0, sizeof(vis));
    pq.push({1, u});
    long long sum = 0;
    vis[u] = 1;
        while(!pq.empty()) {
        ii frt = pq.front();
        pq.pop();
        //if(vis[frt.se]) continue;
            sum += frt.fi;
        for(int i = 0; i < graph[frt.se].size(); i++) {
            //cout << graph[u][i] << " " << u << "\n";
            int v = graph[frt.se][i];
            if(!vis[v]) {
                pq.push({frt.fi + 1, v}), vis[v] = 1;
            }
        }
    }
    for(int i = 1; i <= n; i++) {
        if(!vis[i]) return LLONG_MAX;
    }
    return sum;
}

int main() {
    cin.tie(0), ios::sync_with_stdio(0);
    cin >> n;
    for(int i = 1; i <= n; i++) {
        int k, u;
        cin >> k;
        while(k--) {
            cin >> u;
            graph[u].pb(i);
        }
    }
    for(int i = 1; i <= n; i++)
        ans = min(ans, lmao(i));
    cout << ans;
}

Compilation message

bosses.cpp: In function 'long long int lmao(int)':
bosses.cpp:30:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < graph[frt.se].size(); i++) {
                        ~~^~~~~~~~~~~~~~~~~~~~~~

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 604 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 604 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 604 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 2 ms 712 KB Output is correct
9 Correct 2 ms 712 KB Output is correct
10 Correct 3 ms 712 KB Output is correct
11 Correct 2 ms 844 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 604 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 2 ms 712 KB Output is correct
9 Correct 2 ms 712 KB Output is correct
10 Correct 3 ms 712 KB Output is correct
11 Correct 2 ms 844 KB Output is correct
12 Correct 7 ms 844 KB Output is correct
13 Correct 6 ms 844 KB Output is correct
14 Correct 154 ms 844 KB Output is correct
15 Correct 5 ms 844 KB Output is correct
16 Correct 635 ms 1020 KB Output is correct
17 Correct 716 ms 1020 KB Output is correct
18 Correct 675 ms 1020 KB Output is correct