oj.uz

Submission #340234

# Submission time Handle Problem Language Result Execution time Memory
340234 2020-12-27T10:36:32 Z Kerim Bosses (BOI16_bosses) C++17
100 / 100
 870 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 N = 5000+5;
vl g[N],tr[N];
int salary[N];
bool vis[N];
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() {
	solve();return 0;
}

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 7 ms 748 KB Output is correct
13 Correct 6 ms 748 KB Output is correct
14 Correct 212 ms 748 KB Output is correct
15 Correct 67 ms 876 KB Output is correct
16 Correct 672 ms 1004 KB Output is correct
17 Correct 870 ms 876 KB Output is correct
18 Correct 862 ms 876 KB Output is correct