Submission #928525

#	Time	Username	Problem	Language	Result	Execution time	Memory
928525		haru09	Bosses (BOI16_bosses)	C++17	100 / 100	597 ms	102796 KiB

bosses

#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 (stderr)

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 / 22
• Subtask 2: 45 / 45
• Subtask 3: 33 / 33