oj.uz

Submission #951527

# Submission time Handle Problem Language Result Execution time Memory
951527 2024-03-22T05:10:06 Z Faisal_Saqib Bosses (BOI16_bosses) C++17
100 / 100
 1148 ms 1468 KB 
#include <bits/stdc++.h>
using namespace std;
const int N=5e3+10;
set<int> tp[N];
vector<int> ma[N];
int h[N],val[N];
void compute_answer(int&v)
{
    val[v]=0;
    for(int&ap:ma[v])
    {
        compute_answer(ap);
        val[v]+=val[ap];
    }
    val[v]++;
}
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int k;
        cin>>k;
        for(int j=1;j<=k;j++)
        {
            int p;
            cin>>p;
            tp[p].insert(i);
        }
    }
    int ans=1e9;
    for(int i=1;i<=n;i++)
    {
        for(int ap=1;ap<=n;ap++)
        {
            ma[ap].clear();
            h[ap]=1e9;
        }
        {
            //Time = O()
            queue<int> q;
            q.push(i);
            h[i]=0;
            while(q.size())
            {
                int f=q.front();
                q.pop();
                for(auto ap:tp[f])
                {
                    if((h[ap]>(h[f]+1)))
                    {
                        h[ap]=h[f]+1;
                        ma[f].push_back(ap);
                        q.push(ap);
                    }
                }
            }
        }
        compute_answer(i);
        int sum=0;
        for(int i=1;i<=n;i++)
        {
            if(h[i]==1e9)
            {
                sum=1e9;
                break;
            }
            sum+=val[i];
        }
        ans=min(ans,sum);
    }
    cout<<ans<<'\n';
    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 1 ms 604 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 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 0 ms 604 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 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 0 ms 604 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 20 ms 1116 KB Output is correct
13 Correct 14 ms 1116 KB Output is correct
14 Correct 291 ms 1264 KB Output is correct
15 Correct 29 ms 1400 KB Output is correct
16 Correct 1085 ms 1432 KB Output is correct
17 Correct 1147 ms 1468 KB Output is correct
18 Correct 1148 ms 1464 KB Output is correct