oj.uz

Submission #531822

# Submission time Handle Problem Language Result Execution time Memory
531822 2022-03-01T15:31:31 Z devariaota Bosses (BOI16_bosses) C++17
100 / 100
 621 ms 636 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 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 428 KB Output is correct

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 428 KB Output is correct
7 Correct 1 ms 432 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 436 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 4 ms 460 KB Output is correct
13 Correct 3 ms 460 KB Output is correct
14 Correct 121 ms 540 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 466 ms 616 KB Output is correct
17 Correct 606 ms 588 KB Output is correct
18 Correct 621 ms 636 KB Output is correct