| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 884336 |
2023-12-07T07:19:50 Z |
vjudge1 |
Bosses (BOI16_bosses) |
C++17 |
|
462 ms |
3060 KB |
// in the name of God
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define fast() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ff first
#define ss second
#define pb(x) push_back(x)
#define all(x) x.begin(), x.end()
#define mk make_pair
#define ppb pop_back
#define endl '\n'
#define pii pair<int, int>
#define sz(x) (int)x.size()
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O4")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx2")
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int mod = 1e9 + 7, maxn = 1e5 + 10, inf = 1e9 + 1, lg = 25, pp = 4447, modd = 1e9 + 9;
vector<vector<int>> g(maxn);
int n, ans = inf;
void bfs(int v){
vector<int> dist(n, inf);
vector<int> t(n + 1, 0);
dist[v] = 0;
queue<int> q;
q.push(v);
while(q.size()){
int u = q.front();
q.pop();
for(int v : g[u]){
if(dist[v] > dist[u] + 1){
dist[v] = dist[u] + 1;
q.push(v);
}
}
}
for(int i = 0; i < n; ++i){
if(dist[i] == inf) return;
t[dist[i]]++;
}
int x = 0, anss = 0;
for(int i = n; i >= 0; --i){
x += t[i];
anss += x;
}
ans = min(ans, anss);
}
signed main(){
fast();
cin >> n;
for(int i = 0; i < n; ++i){
int t; cin >> t;
for(int j = 0; j < t; ++j){
int u; cin >> u;
u--;
g[u].pb(i);
}
}
for(int i = 0; i < n; ++i){
bfs(i);
}
cout << ans;
}
// Running from the daylight...
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2648 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2904 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2652 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2648 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2904 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 8 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 9 |
Correct |
2 ms |
2652 KB |
Output is correct |
| 10 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 11 |
Correct |
1 ms |
2580 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2648 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2904 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 8 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 9 |
Correct |
2 ms |
2652 KB |
Output is correct |
| 10 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 11 |
Correct |
1 ms |
2580 KB |
Output is correct |
| 12 |
Correct |
5 ms |
2908 KB |
Output is correct |
| 13 |
Correct |
4 ms |
2908 KB |
Output is correct |
| 14 |
Correct |
85 ms |
2908 KB |
Output is correct |
| 15 |
Correct |
9 ms |
3060 KB |
Output is correct |
| 16 |
Correct |
409 ms |
2908 KB |
Output is correct |
| 17 |
Correct |
462 ms |
2904 KB |
Output is correct |
| 18 |
Correct |
457 ms |
2908 KB |
Output is correct |
