# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
928525 | 2024-02-16T14:48:57 Z | haru09 | Bosses (BOI16_bosses) | C++17 | 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
# | 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 |
# | 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 |
# | 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 |