oj.uz

Submission #645922

# Submission time Handle Problem Language Result Execution time Memory
645922 2022-09-28T09:45:06 Z GaLz Bosses (BOI16_bosses) C++14
100 / 100
 586 ms 716 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long ul;
typedef double dbl;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef map<ll, ll> mll;
typedef pair<string, ll> psl;
typedef map<string, ll> msl;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef deque<ll> deq;
typedef priority_queue<ll, vector<ll>, greater<ll>> pqm;
typedef priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> dij;
typedef priority_queue<ll> pq;
typedef string str;
const ll mod=1e9+7;
const ll maxn=5e3+1;
ll gcd(ll a, ll b) {
    return a==0 ? b : gcd(a, b%a);
}
ll lcm(ll a, ll b) {
    ll ans=a*b;
    ans=ans/(gcd(a, b));
    return ans;
}
#define ihacoy ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define dh << endl;
#define co cout <<
#define udh cout << endl;
#define spa << " ";
#define ci cin >>
#define fi first
#define se second
#define sp << " " <<
#define tes while(t--)
#define pb push_back
#define pf push_front
#define pob pop_back()
#define pof pop_front()
#define gre greater<ll>()
#define sip return 0
#define ub upper_bound
#define lb lower_bound
#define bs binary_search
int n, k, x, mini=1e9, fr;
queue<int> qu;
vi adj[maxn];
int main() {
    ihacoy
    ci n;
    for(int i=1; i<=n; i++) {
        ci k;
        for(int j=0; j<k; j++) {
            ci x;
            adj[x].pb(i);
        }
    }
    for(int i=1; i<=n; i++) {
        if(adj[i].empty()) continue;
        vector<bool> vis(n+1);
        qu.push(i);
        vis[i]=1;;
        int node=0, cnt=1, ans=n;
        while(!qu.empty()) {
            fr=qu.front();
            qu.pop();
            node++;
            for(auto it : adj[fr]) {
                if(!vis[it]) {
                    vis[it]=1;
                    qu.push(it);
                }
            }
            cnt--;
            if(cnt==0) {
                ans+=(n-node);
                cnt=(int)qu.size();
            }
        }
        if(node==n) {
            mini=min(mini, ans);
        }
    }
    co mini;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 436 KB Output is correct
4 Correct 1 ms 436 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 5 ms 452 KB Output is correct
13 Correct 3 ms 468 KB Output is correct
14 Correct 110 ms 536 KB Output is correct
15 Correct 2 ms 508 KB Output is correct
16 Correct 454 ms 716 KB Output is correct
17 Correct 586 ms 640 KB Output is correct
18 Correct 578 ms 644 KB Output is correct