Submission #780958

#TimeUsernameProblemLanguageResultExecution timeMemory
7809581075508020060209tcBosses (BOI16_bosses)C++14
100 / 100
1018 ms15056 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define X first #define Y second int n; vector<int>pch[200005]; vector<int>pfa[200005]; vector<int>e[200005]; int dp[200005]; int vis[200005]; int ans; void dfs(int nw){ dp[nw]=1; for(int i=0;i<e[nw].size();i++){ int v=e[nw][i]; dfs(v); dp[nw]+=dp[v]; } } void solve(int rt){ for(int i=1;i<=n;i++){ vis[i]=0; dp[i]=0; e[i].clear(); } vis[rt]=1; queue<int>q; q.push(rt); while(q.size()){ int nw=q.front(); q.pop(); for(int i=0;i<pch[nw].size();i++){ int v=pch[nw][i]; if(vis[v]){continue;} e[nw].push_back(v); vis[v]=1; q.push(v); } } for(int i=1;i<=n;i++){ if(vis[i]==0){return;} } dfs(rt); int cal=0; for(int i=1;i<=n;i++){ cal+=dp[i]; } ans=min(ans,cal); } signed main(){ cin>>n; for(int i=1;i<=n;i++){ int k; cin>>k; for(int j=1;j<=k;j++){ int v; cin>>v; pfa[i].push_back(v); pch[v].push_back(i); } } ans=1e18; for(int i=1;i<=n;i++){ solve(i); } cout<<ans<<endl; }

Compilation message (stderr)

bosses.cpp: In function 'void dfs(long long int)':
bosses.cpp:16:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 | for(int i=0;i<e[nw].size();i++){
      |             ~^~~~~~~~~~~~~
bosses.cpp: In function 'void solve(long long int)':
bosses.cpp:35:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for(int i=0;i<pch[nw].size();i++){
      |                 ~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...