# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
928780 | 2024-02-17T05:43:59 Z | Baizho | Bosses (BOI16_bosses) | C++14 | 1 ms | 2652 KB |
#include <bits/stdc++.h> using namespace std; #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> #pragma GCC optimize("Ofast,unroll-loops,fast-math") #pragma GCC target("popcnt") typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair<ll,ll> pll; #define sz size() #define ff first #define ss second #define all(a) a.begin(),a.end() #define pb push_back const int mod = ll(1e9)+7; //(b + (a%b)) % b (to mod -1%(10^9+7) correctly in c++ its -1 but its suppose to be 10^9+6 const ll MOD = 998244353; // (a%mod)*(binpow(b,mod-2,mod) = (a/b)%mod const int N = ll(1e5)+5; const int M = ll(2e5) + 5; const long long inf = 1e18; const long double eps = 1e-15L; ll lcm(ll a, ll b) { return (a / __gcd(a,b))*b; } ll binpow(ll a, ll b, ll m) { ll res=1; a %= m; while(b>0){ if(b&1)res=(res * a) % m; a=(a * a) % m; b/=2; } return res%m;} void Freopen(string Key){ freopen((Key+".in").c_str(), "r", stdin); freopen((Key+".out").c_str(), "w", stdout); } int n, dis[N]; vector<int> g[N]; void djik(int u) { for(int i = 1; i <= n; i ++) dis[i] = 1e9; dis[u] = 1; queue<int> q; q.push(u); while(!q.empty()) { int v = q.front(); q.pop(); for(auto to : g[v]) { if(dis[to] > dis[v] + 1) { q.push(to); dis[to] = dis[v] + 1;; } } } } void Baizho() { cin>>n; for(int i = 1; i <= n; i ++) { int k; cin>>k; while(k --) { int to; cin>>to; g[to].pb(i); } } int ans = 2e9; for(int i = 1; i <= n; i ++) { djik(i); int sum = 0; for(int j = 1; j <= n; j ++) sum += dis[j]; ans = min(ans, sum); } cout<<ans; } signed main() { // Freopen("nondec"); ios_base::sync_with_stdio(false); cin.tie(0);cout.tie(0); // precalc(); int ttt = 1; // cin>>ttt; for(int i=1; i<=ttt; i++) {Baizho(); } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2652 KB | Output is correct |
2 | Correct | 1 ms | 2652 KB | Output is correct |
3 | Correct | 1 ms | 2652 KB | Output is correct |
4 | Incorrect | 1 ms | 2652 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2652 KB | Output is correct |
2 | Correct | 1 ms | 2652 KB | Output is correct |
3 | Correct | 1 ms | 2652 KB | Output is correct |
4 | Incorrect | 1 ms | 2652 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2652 KB | Output is correct |
2 | Correct | 1 ms | 2652 KB | Output is correct |
3 | Correct | 1 ms | 2652 KB | Output is correct |
4 | Incorrect | 1 ms | 2652 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |