oj.uz

Submission #885531

# Submission time Handle Problem Language Result Execution time Memory
885531 2023-12-10T02:25:54 Z cpptowin Bosses (BOI16_bosses) C++17
67 / 100
 1500 ms 71204 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 1010
#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[maxn];
vi adj[maxn];
int sz[maxn],vis[maxn];
int cnt,cost;
int h[maxn];
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 23 ms 70748 KB Output is correct
2 Correct 22 ms 70748 KB Output is correct
3 Correct 26 ms 70748 KB Output is correct
4 Correct 27 ms 70748 KB Output is correct
5 Correct 27 ms 70748 KB Output is correct
6 Correct 26 ms 70744 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 70748 KB Output is correct
2 Correct 22 ms 70748 KB Output is correct
3 Correct 26 ms 70748 KB Output is correct
4 Correct 27 ms 70748 KB Output is correct
5 Correct 27 ms 70748 KB Output is correct
6 Correct 26 ms 70744 KB Output is correct
7 Correct 152 ms 70992 KB Output is correct
8 Correct 88 ms 70996 KB Output is correct
9 Correct 55 ms 70896 KB Output is correct
10 Correct 159 ms 70744 KB Output is correct
11 Correct 159 ms 70896 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 70748 KB Output is correct
2 Correct 22 ms 70748 KB Output is correct
3 Correct 26 ms 70748 KB Output is correct
4 Correct 27 ms 70748 KB Output is correct
5 Correct 27 ms 70748 KB Output is correct
6 Correct 26 ms 70744 KB Output is correct
7 Correct 152 ms 70992 KB Output is correct
8 Correct 88 ms 70996 KB Output is correct
9 Correct 55 ms 70896 KB Output is correct
10 Correct 159 ms 70744 KB Output is correct
11 Correct 159 ms 70896 KB Output is correct
12 Correct 314 ms 71052 KB Output is correct
13 Correct 225 ms 71100 KB Output is correct
14 Execution timed out 1597 ms 71204 KB Time limit exceeded
15 Halted 0 ms 0 KB -