oj.uz

Submission #446138

# Submission time Handle Problem Language Result Execution time Memory
446138 2021-07-21T04:52:18 Z kym Bosses (BOI16_bosses) C++14
100 / 100
 1254 ms 1092 KB 
#include <bits/stdc++.h>
using namespace std;
#define int ll 
#define FOR(i,s,e) for(ll i = s; i <= (ll)e; ++i)
#define DEC(i,s,e) for(ll i = s; i >= (ll)e; --i)
#define IAMSPEED ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
#define db(x) cerr << #x << "=" << x << "\n"
#define db2(x, y) cerr << #x << "=" << x << " , " << #y << "=" << y << "\n"
#define db3(a,b,c) cerr<<#a<<"="<<a<<","<<#b<<"="<<b<<","<<#c<<"="<<c<<"\n"
#define dbv(v) cerr << #v << ":"; for (auto ite : v) cerr << ite << ' '; cerr <<"\n"
#define dbvp(v) cerr << #v << ":"; for (auto ite : v) cerr << "{"  << ite.f << ',' << ite.s << "} "; cerr << "\n"
#define dba(a,ss,ee) cerr << #a << ":"; FOR(ite,ss,ee) cerr << a[ite] << ' '; cerr << "\n"
#define reach cerr << "LINE: " << __LINE__ << "\n";
#else
#define db(x)
#define db2(x,y)
#define db3(a,b,c)
#define dbv(v)
#define dbvp(v)
#define dba(a,ss,ee)
#define reach 
#endif
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define ll long long 
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define f first
#define s second
#define g0(x) get<0>(x)
#define g1(x) get<1>(x)
#define g2(x) get<2>(x)
#define g3(x) get<3>(x)
typedef pair <ll, ll> pi;
typedef tuple<ll,ll,ll> ti3;
typedef tuple<ll,ll,ll,ll> ti4;
ll rand(ll a, ll b) { return a + rng() % (b-a+1); }
const int MOD = 1e9 + 7;
const int inf = (int)1e9 + 500;
const long long oo = (ll)1e18 + 500;
template <typename T> bool chmax(T& a, const T b) { return a<b ? a = b, 1 : 0; }
template <typename T> bool chmin(T& a, const T b) { return a>b ? a = b, 1 : 0; }
const int MAXN = 5005;
int n;
vector<int> children[MAXN];
int val[MAXN];
bool vis[MAXN];
int par[MAXN];
int ans = oo;
void root(int r) {
	memset(val,0,sizeof val);
	memset(vis,0,sizeof vis);
	memset(par,0,sizeof par);
	queue<int> q;
	vector<int>ord;
	vis[r]=1;
	for(q.push(r);q.size();q.pop()) {
		int x=q.front();
		ord.pb(x);
		for(auto v:children[x]) {
			if(vis[v])continue;
			vis[v] = 1;
			q.push(v);
			par[v] = x;
		}
	}
	while(ord.size()) {
		int x = ord.back(); ord.pop_back();
		val[x]++;
		val[par[x]]+=val[x];
	}
	int s=0;
	FOR(i,1,n){
		s+=val[i];
		if(!vis[i])return;
	}
	chmin(ans,s);
}

int32_t main() 
{
	IAMSPEED
	cin>> n;
	FOR(i,1,n) {
		int k; cin >> k;
		FOR(j,1,k) {
			int x; cin >> x;
			children[x].pb(i);
		}
		
	}
	FOR(i,1,n) root(i);
	cout<<ans;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 444 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 460 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 444 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 7 ms 588 KB Output is correct
13 Correct 5 ms 716 KB Output is correct
14 Correct 257 ms 736 KB Output is correct
15 Correct 19 ms 716 KB Output is correct
16 Correct 878 ms 936 KB Output is correct
17 Correct 1254 ms 1076 KB Output is correct
18 Correct 1249 ms 1092 KB Output is correct