# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
81071 | xiaowuc1 | Bosses (BOI16_bosses) | C++14 | 578 ms | 1444 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
/*
unsigned seed1 = std::chrono::system_clock::now().time_since_epoch().count();
mt19937 g1.seed(seed1);
ios_base::sync_with_stdio(false);
cin.tie(NULL);
*/
using namespace std;
const double PI = 2 * acos(0);
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<int, ll> pill;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef vector<vector<ll>> matrix;
int n;
vector<int> edges[5005];
int dist[5005];
int q[5005];
int solve(int curr) {
for(int i = 1; i <= n; i++) {
dist[i] = 1 << 25;
}
dist[curr] = 0;
int ql = 0;
int qr = 0;
q[qr++] = curr;
int ret = 0;
while(ql < qr) {
curr = q[ql++];
ret += dist[curr];
for(int out: edges[curr]) {
if(dist[out] == 1 << 25) {
dist[out] = dist[curr] + 1;
q[qr++] = out;
}
}
}
if(ql != n) ret = 1 << 30;
return ret;
}
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
int k;
scanf("%d", &k);
while(k--) {
int t;
scanf("%d", &t);
edges[t].push_back(i);
}
}
int ret = 1 << 30;
for(int i = 1; i <= n; i++) {
ret = min(ret, solve(i));
}
printf("%d\n", ret + n);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |