oj.uz

Submission #338186

# Submission time Handle Problem Language Result Execution time Memory
338186 2020-12-22T16:08:54 Z aloo123 Bosses (BOI16_bosses) C++14
100 / 100
 838 ms 1004 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pl = pair<ll,ll>;
using vl = vector<ll>; 
#define mp make_pair
#define f first
#define s second
 
// vectors
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define ins insert 
#define pf push_front 
#define pb push_back
 
// loops
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
 
const int MOD = 1e9+7; // 998244353;
const ll INF = 1e18; // not too close to LLONG_MAX
#define int ll
const int xd[4] = {1,0,-1,0}, yd[4] = {0,1,0,-1}; // for every grid problem!!

const int N = 5000+5;
vl g[N],tr[N];
int salary[N];
bool vis[N];
void dfs(int u,int p){
    salary[u] = 1;
    trav(v,tr[u]){
        if(v == p) continue;
        dfs(v,u);
        salary[u] += salary[v];
    }
}
void solve(){
    int n;
    cin >> n;
    FOR(i,1,n+1){
        int k;
        cin >> k;
        FOR(j,1,k+1){
            int p;cin >> p;
            g[p].pb(i);
        }
    }  
    int ans=  INF;
    FOR(i,1,n+1){
        // root the tree at this node and run a dfs
        // salary[u] = sum salary[v] + 1
        FOR(j,1,n+1){
            vis[j] = 0;
            salary[j] = -1;
        }
        queue<int> q;
        q.push(i);
        vis[i] = 1;
        salary[i] = 1;
        while(!q.empty()){
            int u = q.front();
            q.pop();
            trav(v,g[u]){
                if(vis[v] == 0){
                    vis[v] = 1;
                    q.push(v);
                    salary[v] = salary[u] + 1;
                }
            }
        }
        int sum = 0;
        bool gg = 1;
        FOR(j,1,n+1) sum += salary[j],gg &= (salary[j] > 0);
        if(gg)
            ans = min(ans,sum); 
    }
    cout << ans << "\n";

}

signed main() {
	cin.tie(0)->sync_with_stdio(0);
	cout.tie(0);
	// you should actually read the stuff at the bottom
	int t=1;
	// cin >> t;
	while(t--){
		solve();
	}
}
/* stuff you should look for
	* read the probem 3 more times in case of WA :)
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
	* DON'T GET STUCK ON ONE APPROACH
*/

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 1 ms 620 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 1 ms 620 KB Output is correct
7 Correct 1 ms 620 KB Output is correct
8 Correct 1 ms 620 KB Output is correct
9 Correct 1 ms 620 KB Output is correct
10 Correct 1 ms 620 KB Output is correct
11 Correct 1 ms 620 KB Output is correct
12 Correct 6 ms 748 KB Output is correct
13 Correct 4 ms 748 KB Output is correct
14 Correct 209 ms 748 KB Output is correct
15 Correct 66 ms 876 KB Output is correct
16 Correct 651 ms 1004 KB Output is correct
17 Correct 837 ms 1004 KB Output is correct
18 Correct 838 ms 1004 KB Output is correct