oj.uz

답안 #307355

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
307355 2020-09-27T23:55:22 Z brkdnmz Bosses (BOI16_bosses) C++17
100 / 100
 907 ms 1664 KB 
#include <iostream>
#include <fstream>
#include <cstdio>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <stack>
#include <queue>
#include <algorithm>
#include <string.h>
#include <string>
#include <math.h>
#include <iomanip>
#include <cassert>
#include <random>
using namespace std;

#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
#define REVERSE(v) reverse((v).begin(), (v).end())
#define pb push_back
#define FOR(i, n) for(int i = 0; i < (n); i++)
typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;

const int mod = 1e9 + 7;
const int mod2 = 998244353;

void fact_init(int n);
ll exp(ll taban, ll us, ll md);
ll ebob(ll a, ll b);
ll ekok(ll a, ll b);
ll komb(ll a, ll b);

vector<ll> fact;
vector<ll> inv_fact;
void fact_init(int n, int md){
    fact.resize(n+5);
    inv_fact.resize(n+5);
    fact[0] = inv_fact[0] = 1;
    for(int i = 1; i <= n; i++){
        fact[i] = (fact[i-1] * i) % md;
        inv_fact[i] = exp(fact[i], md-2, md);
    }
}
ll exp(ll taban, ll us, ll md) {
    ll carpan = taban % md;
    if(carpan == 0) return 0;
    ll temp = us;
    ll res = 1;
    while(temp){
        if(temp % 2) res = (res*carpan) % md;
        temp /= 2;
        carpan = (carpan*carpan) % md;
    }
    return res;
}
 
ll ebob(ll a, ll b){
    if(!a)return b;
    return ebob(b%a, a);
}

ll ekok(ll a, ll b){
    return (a*b)/ebob(a, b);
}

ll komb(int a, int b, int md){
    if(a < b) return 0;
    return fact[a] * (inv_fact[a-b] * inv_fact[b] % md) % md;
}
const int N = 5e3 + 5;
vector<int> rev[N];
vector<int> level[N];
int main(){
    ios::sync_with_stdio(false); cin.tie(NULL);
	int n; cin>>n;
	for(int i = 1; i <= n; i++){
		int k; cin>>k;
		for(int j = 0; j < k; j++){
			int s; cin>>s;
			rev[s].pb(i);
		}
	}
	int ans = 1e9;
	for(int root = 1; root <= n; root++){
		FOR(i, N) level[i].clear();
		level[1].pb(root);
		bool vis[N] = {};
		int cur = 0;
		for(int i = 1; i <= n; i++){
			for(auto x: level[i]){
				cur += i;
				vis[x] = true;
				for(auto child: rev[x]){
					if(vis[child]) continue;
					vis[child] = true;
					level[i+1].pb(child);
				}
			}
		}
		bool ok = true;
		for(int i = 1; i <= n; i++) ok &= vis[i];
		if(!ok) continue;
		ans = min(ans, cur);
	}
	cout<<ans<<"\n";
}

Subtask #1
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 640 KB Output is correct
6 Correct 1 ms 640 KB Output is correct

Subtask #2
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 640 KB Output is correct
6 Correct 1 ms 640 KB Output is correct
7 Correct 2 ms 640 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 512 KB Output is correct

Subtask #3
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 640 KB Output is correct
6 Correct 1 ms 640 KB Output is correct
7 Correct 2 ms 640 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 6 ms 640 KB Output is correct
13 Correct 6 ms 768 KB Output is correct
14 Correct 317 ms 848 KB Output is correct
15 Correct 186 ms 836 KB Output is correct
16 Correct 728 ms 896 KB Output is correct
17 Correct 900 ms 1664 KB Output is correct
18 Correct 907 ms 1528 KB Output is correct