oj.uz

Submission #861310

# Submission time Handle Problem Language Result Execution time Memory
861310 2023-10-16T02:19:42 Z nnhzzz Bosses (BOI16_bosses) C++14
100 / 100
 451 ms 852 KB 
#include<bits/stdc++.h>

using namespace std;

#define REP(i,a,b) for(int i = (a); i<=(b); ++i)
#define REPD(i,a,b) for(int i = (a); i>=(b); --i)
#define REPDIS(i,a,b,c) for(int i = (a); i<=(b); i += c)
#define task "test"
#define task1 "nnhzzz"
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) (int)(x).size()
#define MASK(x) (1LL<<x)
#define BIT(x,i) ((x>>i)&1LL)
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int,int>
#define vpii vector<pii>
#define fi first
#define se second
#define ld long double
#define ll long long

//-------------------------------------------------------------------------------//
template<typename T> bool mini(T &a, T b){if(a>b){a=b;return true;}return false;}
template<typename T> bool maxi(T &a, T b){if(a<b){a=b;return true;}return false;}
//-------------------------------------------------------------------------------//
const int MAXN = 5e3+7,N = 1e5+7,inf = 1e9,LOG = 20;
const int MOD = 1e9+7,MOD1 = 123456789;
//-------------------------------------------------------------------------------//

vi adj[MAXN];

void solve(){
    int res = inf,n; cin >> n;
    REP(i,1,n){
        int k; cin >> k;
        while(k--){
            int j; cin >> j;
            adj[j].push_back(i);
        }
    }
    REP(s,1,n){
        queue<int> q; q.push(s);
        vi dep(n+3,0); dep[s] = 1;
        int ma = 1;
        while(SZ(q)!=0){
            int u = q.front(); q.pop();
            REP(i,0,SZ(adj[u])-1){
                int v = adj[u][i];
                if(dep[v]!=0) continue;
                dep[v] = dep[u]+1;
                maxi(ma,dep[v]);
                q.push(v);
            }
        }
        int sum = 0;
        REP(i,1,n){
            if(dep[i]==0) sum = inf;
            sum += dep[i];
        }
        mini(res,sum);
    }
    cout << res;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if(fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    if(fopen(task1".inp","r")){
        freopen(task1".inp","r",stdin);
        freopen(task1".out","w",stdout);
    }
    solve();
    return 0;
}

Compilation message

bosses.cpp: In function 'int main()':
bosses.cpp:70:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
bosses.cpp:71:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
bosses.cpp:74:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |         freopen(task1".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
bosses.cpp:75:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |         freopen(task1".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 576 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 576 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 4 ms 604 KB Output is correct
13 Correct 3 ms 604 KB Output is correct
14 Correct 88 ms 604 KB Output is correct
15 Correct 18 ms 604 KB Output is correct
16 Correct 451 ms 768 KB Output is correct
17 Correct 436 ms 796 KB Output is correct
18 Correct 444 ms 852 KB Output is correct