oj.uz

Submission #68902

# Submission time Handle Problem Language Result Execution time Memory
68902 2018-08-19T08:11:36 Z alenam0161 Bosses (BOI16_bosses) C++17
22 / 100
 3 ms 816 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N = 5007;
vector<int> g[N],g1[N];
bool used[N];
int cur=0;
int dfs(int v,int p=-1){
	int x=0;
	for(int to:g1[v]){
		if(to==p)continue;
		x+=dfs(to,v);
	}
	cur+=x+1;
	return x+1;
}
int main()
{
    int n;
    scanf("%d",&n);
    pair<int,int> mb={-1e9,-1e9};
    for(int i=1;i<=n;++i){
		int k;
		scanf("%d",&k);
		for(int j=0;j<k;++j){
			int p;
			scanf("%d",&p);
			g[p].pb(i);
			mb=max(mb,{(int)g[p].size(),p});
		}
	}
	int ans=1e9;
	for(int i=1;i<=n;++i){
		if(g[i].size()==0)continue;
		if(g[i].size()!=mb.first)continue;
		for(int j=1;j<=n;++j)g1[j].resize(0);
		queue<int> q;
		q.push(i);
		memset(used,0,sizeof(used));
		used[i]=true;
		int hw=1;
		while(!q.empty()){
			int v=q.front();q.pop();
			for(auto to:g[v]){
				if(used[to]==true)continue;
				g1[v].pb(to);
				q.push(to);
				used[to]=true;
				hw++;
			}
		}
		if(hw==n){
			cur=0;
			dfs(i);
			ans=min(ans,cur);
		}
	}
	cout<<ans<<endl;
    return 0;
}

Compilation message

bosses.cpp: In function 'int main()':
bosses.cpp:35:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(g[i].size()!=mb.first)continue;
      ~~~~~~~~~~~^~~~~~~~~~
bosses.cpp:20:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
bosses.cpp:24:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&k);
   ~~~~~^~~~~~~~~
bosses.cpp:27:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&p);
    ~~~~~^~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 3 ms 612 KB Output is correct
3 Correct 3 ms 612 KB Output is correct
4 Correct 3 ms 816 KB Output is correct
5 Correct 3 ms 816 KB Output is correct
6 Correct 3 ms 816 KB Output is correct

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 3 ms 612 KB Output is correct
3 Correct 3 ms 612 KB Output is correct
4 Correct 3 ms 816 KB Output is correct
5 Correct 3 ms 816 KB Output is correct
6 Correct 3 ms 816 KB Output is correct
7 Incorrect 3 ms 816 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 3 ms 612 KB Output is correct
3 Correct 3 ms 612 KB Output is correct
4 Correct 3 ms 816 KB Output is correct
5 Correct 3 ms 816 KB Output is correct
6 Correct 3 ms 816 KB Output is correct
7 Incorrect 3 ms 816 KB Output isn't correct
8 Halted 0 ms 0 KB -