# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
970844 | 2024-04-27T11:21:45 Z | hariaakas646 | Bosses (BOI16_bosses) | C++14 | 420 ms | 944 KB |
#pragma GCC optimize("O3","unroll-loops") #include <bits/stdc++.h> using namespace std; #define scd(t) scanf("%d", &t) #define sclld(t) scanf("%lld", &t) #define forr(i, j, k) for (int i = j; i < k; i++) #define frange(i, j) forr(i, 0, j) #define all(cont) cont.begin(), cont.end() #define mp make_pair #define pb push_back #define f first #define s second typedef long long int lli; typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<bool> vb; typedef vector<lli> vll; typedef vector<string> vs; typedef vector<pii> vii; typedef vector<vi> vvi; typedef map<int, int> mpii; typedef set<int> seti; typedef multiset<int> mseti; typedef long double ld; void usaco() { freopen("/media/hariaakash646/785EF1075EF0BF46/CompetitiveProgramming/input.in", "r", stdin); // freopen("problem.out", "w", stdout); } vvi graph; vvi tree; vb vis; int tot = 0; int dfs(int x) { int v = 1; for(auto e : tree[x]) { v += dfs(e); } tot += v; return v; } int main() { // usaco(); int n; scd(n); graph = vvi(n+1); forr(i, 1, n+1) { int k; scd(k); frange(_, k) { int b; scd(b); graph[b].pb(i); } } int mi = 2e9; forr(i, 1, n+1) { // vis = vb(n+1); // tree = vvi(n+1); queue<pii> q; vi depth(n+1); q.push(mp(i, 0)); tot = 0; while(q.size()) { auto p = q.front(); q.pop(); if(depth[p.f]) continue; // tree[p.s].pb(p.f); depth[p.f] = depth[p.s]+1; tot += depth[p.f]; for(auto e : graph[p.f]) q.push(mp(e, p.f)); } bool done = true; forr(j, 1, n+1) done = done && (bool)depth[j]; if(done) { mi = min(mi, tot); } } printf("%d", mi); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 1 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 0 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 1 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 0 ms | 348 KB | Output is correct |
7 | Correct | 0 ms | 348 KB | Output is correct |
8 | Correct | 0 ms | 348 KB | Output is correct |
9 | Correct | 0 ms | 408 KB | Output is correct |
10 | Correct | 1 ms | 348 KB | Output is correct |
11 | Correct | 1 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 1 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 0 ms | 348 KB | Output is correct |
7 | Correct | 0 ms | 348 KB | Output is correct |
8 | Correct | 0 ms | 348 KB | Output is correct |
9 | Correct | 0 ms | 408 KB | Output is correct |
10 | Correct | 1 ms | 348 KB | Output is correct |
11 | Correct | 1 ms | 348 KB | Output is correct |
12 | Correct | 9 ms | 604 KB | Output is correct |
13 | Correct | 7 ms | 604 KB | Output is correct |
14 | Correct | 70 ms | 664 KB | Output is correct |
15 | Correct | 6 ms | 604 KB | Output is correct |
16 | Correct | 413 ms | 776 KB | Output is correct |
17 | Correct | 398 ms | 944 KB | Output is correct |
18 | Correct | 420 ms | 772 KB | Output is correct |