# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
42385 | 2018-02-26T15:33:05 Z | Hassoony | Bosses (BOI16_bosses) | C++11 | 2 ms | 608 KB |
#include<bits/stdc++.h> #include<unordered_map> #define F first #define S second using namespace std; typedef long long ll; typedef long double D; const ll inf=(1ll<<61); const ll mod=1e9+7; const int MX=5002; int n,k,x; bool vis[MX]; int val[MX],par[MX],in[MX]; vector<int>v[MX],v1[MX]; int ans,mn=1e9; void dfs(int x){ if(v1[x].size()==0){ val[x]=1; ans++; vis[x]=1; return; } if(vis[x])return; vis[x]=1; int &ret=val[x]; for(auto pp:v1[x]){ if(vis[pp])continue; dfs(pp); ret+=val[pp]; } ++ret; ans+=ret; } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&k); while(k--){ scanf("%d",&x); v[x].push_back(i); } } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++)vis[j]=0,val[j]=0; queue<int>q; q.push(i); while(!q.empty()){ int x=q.front();q.pop(); vis[x]=1; for(auto pp:v[x]){ if(vis[pp])continue; par[pp]=x; in[x]=1; vis[pp]=1; q.push(pp); } } bool b=1; for(int j=1;j<=n;j++){ if(!vis[j])b=0; } if(!b)continue; for(int j=1;j<=n;j++)vis[j]=0; for(int j=1;j<=n;j++){ if(!in[j])q.push(j),val[j]=1,vis[j]=1; } if(q.empty())continue; while(!q.empty()){ int x=q.front();q.pop(); if(!vis[par[x]]){ q.push(par[x]); val[par[x]]+=val[x]; vis[par[x]]=1; } } ans=0; for(int j=1;j<=n;j++)ans+=val[j]+1; mn=min(mn,ans); } printf("%d\n",mn); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 504 KB | Output is correct |
2 | Incorrect | 2 ms | 608 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 504 KB | Output is correct |
2 | Incorrect | 2 ms | 608 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 504 KB | Output is correct |
2 | Incorrect | 2 ms | 608 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |