oj.uz

Submission #885532

# Submission time Handle Problem Language Result Execution time Memory
885532 2023-12-10T02:26:30 Z cpptowin Bosses (BOI16_bosses) C++17
100 / 100
 448 ms 1280 KB 
#include<bits/stdc++.h>
#define fo(i,d,c) for(int i=d;i<=c;i++)
#define fod(i,c,d) for(int i=c;i>=d;i--)
#define maxn 1000010
#define N 5010
#define fi first
#define se second
#define pb emplace_back
#define en cout<<"\n";
#define int long long
#define inf (int)1e18
#define pii pair<int,int>
#define vii vector<pii>
#define lb(x) x&-x
#define bit(i,j) ((i>>j)&1)
#define offbit(i,j) (i^(1<<j))
#define onbit(i,j) (i|(1<<j))
#define vi vector<int>
template <typename T1, typename T2> bool minimize(T1 &a, T2 b){if (a > b) {a = b; return true;} return false;}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b){if (a < b) {a = b; return true;} return false;}
using namespace std;
int n;
vi ke[N];
vi adj[N];
int sz[N],vis[N];
int cnt,cost;
int h[N];
void bfs(int inp)
{
    cost = cnt = 0;
    memset(h,0,sizeof h);
    memset(sz,0,sizeof sz);
    memset(vis,0,sizeof vis);
    queue<int> q;
    q.push(inp);
    vis[inp] = 1;
    h[inp] = 1;
    cost = 1;
    while(q.size())
    {
        int u = q.front();
        q.pop();
        for(int v : ke[u])
        {
            if(!vis[v])
            {
                h[v] = h[u] + 1;
                cost += h[v];
                vis[v] = 1;
                cnt++;
                q.push(v);
            }
        }
    }
}
main()
{
    #define name "TASK"
    if(fopen(name".inp","r"))
    {
       freopen(name".inp","r",stdin);
       freopen(name".out","w",stdout);
    }
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    cin >> n;
    fo(i,1,n)
    {
        int k;
        cin >> k;
        fo(_,1,k)
        {
            int x;
            cin >> x;
            ke[x].pb(i);
        }
    }
    int ans = inf;
    fo(i,1,n)
    {
        bfs(i);
        if(cnt != n - 1) continue;
        ans = min(ans,cost);
    }
    cout << ans;
}

Compilation message

bosses.cpp:56:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   56 | main()
      | ^~~~
bosses.cpp: In function 'int main()':
bosses.cpp:61:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |        freopen(name".inp","r",stdin);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
bosses.cpp:62:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |        freopen(name".out","w",stdout);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 0 ms 600 KB Output is correct
5 Correct 0 ms 600 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 832 KB Output is correct
9 Correct 0 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 3 ms 860 KB Output is correct
13 Correct 3 ms 860 KB Output is correct
14 Correct 87 ms 880 KB Output is correct
15 Correct 8 ms 860 KB Output is correct
16 Correct 448 ms 1280 KB Output is correct
17 Correct 442 ms 1016 KB Output is correct
18 Correct 434 ms 1012 KB Output is correct