Submission #42379

#TimeUsernameProblemLanguageResultExecution timeMemory
42379HassoonyBosses (BOI16_bosses)C++11
67 / 100
1544 ms1252 KiB
#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=5009; int n,k,x,vis[MX],val[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++)v1[j].clear(),vis[j]=0,val[j]=0; ans=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; v1[x].push_back(pp); vis[pp]=1; q.push(pp); } } for(int j=1;j<=n;j++)vis[j]=0; dfs(i); bool b=1; for(int j=1;j<=n;j++){ if(!vis[j])b=0; } if(b)mn=min(mn,ans); } printf("%lld\n",mn); }

Compilation message (stderr)

bosses.cpp: In function 'int main()':
bosses.cpp:64:23: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'int' [-Wformat=]
     printf("%lld\n",mn);
                       ^
bosses.cpp:33:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
                   ^
bosses.cpp:35:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&k);
                       ^
bosses.cpp:37:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&x);
                           ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...