oj.uz

Submission #208060

# Submission time Handle Problem Language Result Execution time Memory
208060 2020-03-10T00:07:29 Z Blerargh Bosses (BOI16_bosses) C++17
100 / 100
 1332 ms 1144 KB 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> ii;
typedef pair<ld,ld> id;
 
#define FOR(i, a, b) for(int i=(a); i<=(b); i++)
#define ROF(i, a, b) for(int i=(a); i>=(b); i--)
#define MEM(x, v) memset(x, v, sizeof(x))
#define SORT(x) sort((x).begin(), (x).end())
#define CMPSORT(x, cp) sort((x).begin(), (x).end(), cp)
#define FAST ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define getchar_unlocked _getchar_nolock
 
#define f first
#define s second
#define ins insert
#define e emplace
#define eb emplace_back
#define ef emplace_front
#define p push
#define pf push_front
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define ft front
#define bk back
#define pp pop
#define ppb pop_back
#define ppf pop_front
 
#define db cout<<"YEET\n";
#define ct(x) cout<<x<<'\n';
 
const ll MOD = 1e9+7; //998244353
const ll MX = 2e5+5;
const ll INF = 1e18;
const ld PI = acos((ld)-1);
 
vector<ll> dfsadjlist[5005], adjlist[5005];
ll preorder[5005], idx=0, salary=0, cnt;
ll n, k, x;
ll minn=INF;
bool visited[5005];
queue<ll> bfs;
 
 
void dfs(ll node, ll parent){
    preorder[node] = ++idx;
    for (auto edge : dfsadjlist[node]){
        if (edge != parent) dfs(edge, node);
    }
    ll subtreesize = idx-preorder[node]+1;
    salary+=subtreesize;
    return;
}
 
int main(){ 
    FAST
    cin >> n;
    FOR(i, 1, n){
        cin >> k;
        FOR(j, 1, k){
            cin >> x;
            adjlist[x].pb(i);
        }
    }
 
    FOR(i, 1, n){
        MEM(visited, 0);
        FOR(j, 1, n) dfsadjlist[j].clear();
 
        cnt=0;
        bfs.e(i);
        visited[i]=1;
        while (!bfs.empty()){
            ll node = bfs.ft();
            cnt++;
            bfs.pp();
            for (auto edge : adjlist[node]){
                if (visited[edge]) continue;
                bfs.e(edge);
                visited[edge]=1;
                dfsadjlist[node].pb(edge);
            }
        }
 
        if (cnt != n) continue;
        salary=0;
        dfs(i, i);
        minn=min(minn, salary);
    }
    cout << minn;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 632 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 5 ms 632 KB Output is correct
4 Correct 5 ms 504 KB Output is correct
5 Correct 5 ms 632 KB Output is correct
6 Correct 5 ms 632 KB Output is correct
7 Correct 5 ms 632 KB Output is correct
8 Correct 5 ms 632 KB Output is correct
9 Correct 5 ms 632 KB Output is correct
10 Correct 5 ms 632 KB Output is correct
11 Correct 5 ms 632 KB Output is correct
12 Correct 10 ms 760 KB Output is correct
13 Correct 8 ms 888 KB Output is correct
14 Correct 170 ms 1016 KB Output is correct
15 Correct 24 ms 888 KB Output is correct
16 Correct 637 ms 1024 KB Output is correct
17 Correct 1332 ms 1144 KB Output is correct
18 Correct 1325 ms 1144 KB Output is correct