oj.uz

Submission #928525

# Submission time Handle Problem Language Result Execution time Memory
928525 2024-02-16T14:48:57 Z haru09 Bosses (BOI16_bosses) C++17
100 / 100
 597 ms 102796 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define task "code"

const int ar=5e3+5;
const ll mod=1e9+7;
int n;
vector<int> ad[ar];
bool ok[ar][ar];
int dp[ar][ar];
queue<int> pq[ar];
void dijkstra(int u)
{
    memset(dp[u],0x3f,sizeof dp[u]);
    dp[u][u]=1;
    pq[1].push(u);
    for (int d=1;d<=n;d++)
    {
        while(pq[d].size())
        {
            int v=pq[d].front();
            pq[d].pop();
            if (dp[u][v]<d) continue;
            for (auto nv:ad[v])
            {
                int w=dp[u][v]+1;
                if (dp[u][nv]>w)
                {
                    dp[u][nv]=w;
                    pq[w].push(nv);
                }
            }
        }
    }
}
ll ans=1e18;
int main()
{
    ios_base::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);
    }
    cin>>n;
    for (int i=1;i<=n;i++)
    {
        int k;
        cin>>k;
        for (int j=1;j<=k;j++)
        {
            int v;
            cin>>v;
            ad[v].push_back(i);
        }
    }
    for (int i=1;i<=n;i++)
    {
        dijkstra(i);
        ll sum=0;
        for (int j=1;j<=n;j++)
        {
            sum+=dp[i][j];
        }
        ans=min(ans,sum);
    }
    cout<<ans;
}

Compilation message

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

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5720 KB Output is correct
2 Correct 2 ms 5724 KB Output is correct
3 Correct 2 ms 5724 KB Output is correct
4 Correct 2 ms 5976 KB Output is correct
5 Correct 2 ms 5976 KB Output is correct
6 Correct 2 ms 5724 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5720 KB Output is correct
2 Correct 2 ms 5724 KB Output is correct
3 Correct 2 ms 5724 KB Output is correct
4 Correct 2 ms 5976 KB Output is correct
5 Correct 2 ms 5976 KB Output is correct
6 Correct 2 ms 5724 KB Output is correct
7 Correct 2 ms 7772 KB Output is correct
8 Correct 2 ms 5792 KB Output is correct
9 Correct 2 ms 5720 KB Output is correct
10 Correct 2 ms 7772 KB Output is correct
11 Correct 3 ms 7768 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5720 KB Output is correct
2 Correct 2 ms 5724 KB Output is correct
3 Correct 2 ms 5724 KB Output is correct
4 Correct 2 ms 5976 KB Output is correct
5 Correct 2 ms 5976 KB Output is correct
6 Correct 2 ms 5724 KB Output is correct
7 Correct 2 ms 7772 KB Output is correct
8 Correct 2 ms 5792 KB Output is correct
9 Correct 2 ms 5720 KB Output is correct
10 Correct 2 ms 7772 KB Output is correct
11 Correct 3 ms 7768 KB Output is correct
12 Correct 7 ms 9820 KB Output is correct
13 Correct 7 ms 7772 KB Output is correct
14 Correct 201 ms 102164 KB Output is correct
15 Correct 75 ms 102496 KB Output is correct
16 Correct 541 ms 102248 KB Output is correct
17 Correct 597 ms 102436 KB Output is correct
18 Correct 553 ms 102796 KB Output is correct