oj.uz

Submission #887181

# Submission time Handle Problem Language Result Execution time Memory
887181 2023-12-14T01:33:27 Z Caubethieunang Bosses (BOI16_bosses) C++14
100 / 100
 799 ms 50124 KB 
#include <bits/stdc++.h>
#define ll long long
#define LOG 19
#define MASK(i) (1LL<<(i))
#define BIT(x,i) (((x)>>(i))&1)
#define FIRST_BIT(mask) __builtin_ctz((mask)&(-mask))
#define ERASE_BIT(mask) (mask)^((mask)&(-mask))
#define left _left
#define right _right
#define task "t"
using namespace std;
const ll INF=1e18;
const int iat=1e6+9;
const int mod=1e9+7;
void fast_IO()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    if(fopen(task".inp","r"))
    {
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
}
int n;
bool visited[iat];
vector <int> g[iat],store[iat];
ll sum,salary[iat];
void dfs(int u)
{
    salary[u]=1;
    for(int v : g[u])dfs(v),salary[u]+=salary[v];
    sum+=salary[u];
}
void bfs(int s)
{
    for(int i=1; i<=n; i++)
    {
        visited[i]=false;
        g[i].clear();
    }
    queue <int> q;
    q.push(s);
    visited[s]=true;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int v : store[u])
        {
            if(!visited[v])
            {
                visited[v]=true;
                g[u].push_back(v);
                q.push(v);
            }
        }
    }
    for(int i=1; i<=n; i++)
    {
        if(!visited[i])
        {
            sum=LLONG_MAX;
            return;
        }
    }
    dfs(s);
}
signed main()
{
    fast_IO();
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        int k;
        cin>>k;
        for(int j=1; j<=k; j++)
        {
            int x;
            cin>>x;
            store[x].push_back(i);
        }
    }
    ll ans=LLONG_MAX;
    for(int i=1; i<=n; i++)
    {
        sum=0;
        bfs(i);
        ans=min(ans,sum);
    }
    cout<<ans;
}

Compilation message

bosses.cpp: In function 'void fast_IO()':
bosses.cpp:22:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
bosses.cpp:23:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 49496 KB Output is correct
2 Correct 10 ms 49500 KB Output is correct
3 Correct 10 ms 49496 KB Output is correct
4 Correct 11 ms 49500 KB Output is correct
5 Correct 10 ms 49500 KB Output is correct
6 Correct 10 ms 49612 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 49496 KB Output is correct
2 Correct 10 ms 49500 KB Output is correct
3 Correct 10 ms 49496 KB Output is correct
4 Correct 11 ms 49500 KB Output is correct
5 Correct 10 ms 49500 KB Output is correct
6 Correct 10 ms 49612 KB Output is correct
7 Correct 10 ms 49968 KB Output is correct
8 Correct 10 ms 49500 KB Output is correct
9 Correct 10 ms 49500 KB Output is correct
10 Correct 11 ms 49644 KB Output is correct
11 Correct 11 ms 49756 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 49496 KB Output is correct
2 Correct 10 ms 49500 KB Output is correct
3 Correct 10 ms 49496 KB Output is correct
4 Correct 11 ms 49500 KB Output is correct
5 Correct 10 ms 49500 KB Output is correct
6 Correct 10 ms 49612 KB Output is correct
7 Correct 10 ms 49968 KB Output is correct
8 Correct 10 ms 49500 KB Output is correct
9 Correct 10 ms 49500 KB Output is correct
10 Correct 11 ms 49644 KB Output is correct
11 Correct 11 ms 49756 KB Output is correct
12 Correct 13 ms 50076 KB Output is correct
13 Correct 13 ms 49756 KB Output is correct
14 Correct 134 ms 50000 KB Output is correct
15 Correct 28 ms 49752 KB Output is correct
16 Correct 504 ms 50024 KB Output is correct
17 Correct 799 ms 50124 KB Output is correct
18 Correct 799 ms 50112 KB Output is correct