Submission #949956

#TimeUsernameProblemLanguageResultExecution timeMemory
949956huangallenBosses (BOI16_bosses)C++17
100 / 100
424 ms856 KiB
#include<bits/stdc++.h> using namespace std; #pragma GCC optimize("O3,unroll-loops") #define int long long #define REP(i,n) for(int i=0;i<n;i++) #define REP1(i,n) for(int i=1;i<=n;i++) #define RREP(i,n) for(int i=(n)-1;i>=0;i--) #define RREP1(i,n) for(int i=(n);i>=1;i--) #define f first #define s second #define pb push_back #define ALL(x) x.begin(),x.end() #define SZ(x) (int)(x.size()) #define SQ(x) (x)*(x) #define pii pair<int,int> #define pipii pair<int,pii> #define Graph vector<vector<int>> #define IOS() ios::sync_with_stdio(0),cin.tie(0) #define md(x) (((x)%(mod)+(mod))%(mod)) #define MD(x,M) (((x)%(M)+(M))%(M)) #define ld long double #define pdd pair<ld,ld> #ifdef LOCAL #define op(x) cout<<(#x)<<"="<<(x)<<", "; #define ope(x) cout<<(#x)<<"="<<(x)<<endl; #define oparr(x) cout<<(#x)<<":";REP(allen,(x).size()) cout<<x[allen]<<" ";cout<<" size="<<(x).size()<<endl; #define entr cout<<endl; #else #define op(x) ; #define ope(x) ; #define oparr(x) ; #define entr ; #endif const int mod=1e9+7; const int maxn=2e5+5; const int maxv=1e5+5; const int inf=(1ll<<62); mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int rd(int l,int r) { return uniform_int_distribution<int>(l,r)(rng); } Graph g; int an=inf; int n; int solve(int root) { queue<int> q; q.push(root); vector<int> lev(n); lev[root]=1; int ret=0; while(q.size()) { int u=q.front(); q.pop(); ret+=lev[u]; for(int v:g[u]) { if(lev[v]) continue; lev[v]=lev[u]+1; q.push(v); } } REP(i,n) if(!lev[i]) return inf; return ret; } signed main() { IOS(); cin>>n; g=Graph(n); REP(i,n) { int k;cin>>k; REP(j,k) { int v; cin>>v; v--; g[v].pb(i); } } REP(i,n) an=min(an,solve(i)); cout<<an<<'\n'; return 0; } /* 4 1 4 3 1 3 4 2 1 2 1 3 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...