oj.uz

Submission #51589

# Submission time Handle Problem Language Result Execution time Memory
51589 2018-06-19T00:30:38 Z thiago4532 Bosses (BOI16_bosses) C++17
0 / 100
 2 ms 668 KB 
#include <bits/stdc++.h>
#define gc getchar
#define rep(i, a, b) for(int i=a;i<=b;i++)
#define rep2(i, a, b) for(int i=a;i>=b;--i)
#define wipe(a, b) memset(a, b, sizeof a);
#define pb push_back

using namespace std;
const int maxn = 5010;
vector<int> bosses[maxn], employ[maxn];
int sz[maxn];

inline int scan(){
	int n=0, x=gc(), s=1;
	for(;x<'0'||x>'9';x=gc()) if(x=='-') s=-1;
	for(;x>='0'&&x<='9';x=gc()) n = 10*n + x - '0';
	return n*s;
}

bool mark[maxn];
int dfs(int u){
	mark[u] = true;
	sz[u] = 1;
	
	vector<int> tutu;
	for(auto v : employ[u]) if(!mark[v]) mark[v] = true, tutu.push_back(v);
	for(auto v : tutu)
		sz[u] += dfs(v);
	return sz[u];
}

int main(){
	ios::sync_with_stdio(false), cin.tie(0);
	int n = scan();
	rep(i, 1, n){
		int k = scan();
		rep(j, 1, k){
			int x = scan();
			bosses[i].push_back(x);
			employ[x].push_back(i);
		}
	}

	int maior=-0x3f3f3f3f, l=0;
	rep(u, 1, n){
		if(maior < (int)employ[u].size()){
			maior = employ[u].size();
			l = u;
		}
	}

	dfs(l);
	int ans=0;
	rep(i, 1, n) ans += sz[i];
	cout << ans << "\n";
	return 0;
}

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 2 ms 632 KB Output is correct
3 Incorrect 2 ms 668 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 2 ms 632 KB Output is correct
3 Incorrect 2 ms 668 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 2 ms 632 KB Output is correct
3 Incorrect 2 ms 668 KB Output isn't correct
4 Halted 0 ms 0 KB -