| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 159620 |
2019-10-23T14:38:35 Z |
socho |
Bosses (BOI16_bosses) |
C++14 |
|
1049 ms |
776 KB |
#include "bits/stdc++.h"
using namespace std;
const int MXN = 5005;
int n;
vector<int> adj[MXN];
int boss(int mo) {
bool vis[MXN];
memset(vis, 0, sizeof vis);
int dist[MXN];
for (int i=0; i<MXN; i++) dist[i] = INT_MAX;
queue<pair<int, int> > topr; // node, dist
topr.push(make_pair(mo, 0));
while (!topr.empty()) {
pair<int, int> nx = topr.front(); topr.pop();
int node = nx.first, dis = nx.second;
dist[node] = dis;
vis[node] = true;
for (int i=0; i<adj[node].size(); i++) {
int other = adj[node][i];
if (!vis[other]) {
vis[other] = true;
topr.push(make_pair(other, dis+1));
}
}
}
int sm = 0;
for (int i=1; i<=n; i++) {
if (dist[i] == INT_MAX) return INT_MAX;
sm += (dist[i] + 1);
}
return sm;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> n;
for (int i=1; i<=n; i++) {
int ac;
cin >> ac;
for (int j=0; j<ac; j++) {
int k;
cin >> k;
adj[k].push_back(i);
}
}
int best = INT_MAX;
for (int i=1; i<=n; i++) {
best = min(best, boss(i));
}
cout << best << endl;
}
Compilation message
bosses.cpp: In function 'int boss(int)':
bosses.cpp:23:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<adj[node].size(); i++) {
~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Correct |
2 ms |
504 KB |
Output is correct |
| 3 |
Correct |
2 ms |
504 KB |
Output is correct |
| 4 |
Correct |
2 ms |
504 KB |
Output is correct |
| 5 |
Correct |
2 ms |
508 KB |
Output is correct |
| 6 |
Correct |
2 ms |
504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Correct |
2 ms |
504 KB |
Output is correct |
| 3 |
Correct |
2 ms |
504 KB |
Output is correct |
| 4 |
Correct |
2 ms |
504 KB |
Output is correct |
| 5 |
Correct |
2 ms |
508 KB |
Output is correct |
| 6 |
Correct |
2 ms |
504 KB |
Output is correct |
| 7 |
Correct |
2 ms |
508 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 |
504 KB |
Output is correct |
| 11 |
Correct |
3 ms |
504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Correct |
2 ms |
504 KB |
Output is correct |
| 3 |
Correct |
2 ms |
504 KB |
Output is correct |
| 4 |
Correct |
2 ms |
504 KB |
Output is correct |
| 5 |
Correct |
2 ms |
508 KB |
Output is correct |
| 6 |
Correct |
2 ms |
504 KB |
Output is correct |
| 7 |
Correct |
2 ms |
508 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 |
504 KB |
Output is correct |
| 11 |
Correct |
3 ms |
504 KB |
Output is correct |
| 12 |
Correct |
7 ms |
632 KB |
Output is correct |
| 13 |
Correct |
6 ms |
632 KB |
Output is correct |
| 14 |
Correct |
220 ms |
636 KB |
Output is correct |
| 15 |
Correct |
17 ms |
632 KB |
Output is correct |
| 16 |
Correct |
792 ms |
724 KB |
Output is correct |
| 17 |
Correct |
1032 ms |
776 KB |
Output is correct |
| 18 |
Correct |
1049 ms |
772 KB |
Output is correct |
