oj.uz

Submission #74897

# Submission time Handle Problem Language Result Execution time Memory
74897 2018-09-07T11:36:18 Z Vardanyan Bosses (BOI16_bosses) C++14
67 / 100
 1500 ms 196404 KB 
//#pragma GCC optimize "-O3"
#include <bits/stdc++.h>
using namespace std;
const long long N = 5001;
bool c[N];
int n;
long long ans = 10000000000000000+7;
long long g[N][N];
long long f[N][N];
int main(){
    scanf("%d",&n);
    for(long long i = 1;i<=n;i++)
        for(long long j = 1;j<=n;j++) f[i][j] = ans;
    for(long long i = 1;i<=n;i++){
        f[i][i] = 0;
        long long ki;
        scanf("%lld",&ki);
        for(long long j = 1;j<=ki;j++){
            long long x;
            scanf("%lld",&x);
            f[x][i] = 1;
        }
    }
    for(long long i = 1;i<=n;i++){
        for(long long j = 1;j<=n;j++){
            for(long long k = 1;k<=n;k++){
                f[j][k] = min(f[j][k],f[j][i]+f[i][k]);
            }
        }
    }

    for(long long i = 1;i<=n;i++){
        long long val = 0;
        for(long long j = 1;j<=n;j++) val+=(f[i][j]+1);
        ans = min(ans,val);
    }
    printf("%lld\n",ans);
    return 0;
}

Compilation message

bosses.cpp: In function 'int main()':
bosses.cpp:11:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
bosses.cpp:17:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",&ki);
         ~~~~~^~~~~~~~~~~~
bosses.cpp:20:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%lld",&x);
             ~~~~~^~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 576 KB Output is correct
4 Correct 2 ms 624 KB Output is correct
5 Correct 2 ms 644 KB Output is correct
6 Correct 2 ms 644 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 576 KB Output is correct
4 Correct 2 ms 624 KB Output is correct
5 Correct 2 ms 644 KB Output is correct
6 Correct 2 ms 644 KB Output is correct
7 Correct 5 ms 1100 KB Output is correct
8 Correct 3 ms 1100 KB Output is correct
9 Correct 2 ms 1100 KB Output is correct
10 Correct 5 ms 1100 KB Output is correct
11 Correct 4 ms 1100 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 576 KB Output is correct
4 Correct 2 ms 624 KB Output is correct
5 Correct 2 ms 644 KB Output is correct
6 Correct 2 ms 644 KB Output is correct
7 Correct 5 ms 1100 KB Output is correct
8 Correct 3 ms 1100 KB Output is correct
9 Correct 2 ms 1100 KB Output is correct
10 Correct 5 ms 1100 KB Output is correct
11 Correct 4 ms 1100 KB Output is correct
12 Correct 17 ms 1800 KB Output is correct
13 Correct 9 ms 1800 KB Output is correct
14 Execution timed out 1575 ms 196404 KB Time limit exceeded
15 Halted 0 ms 0 KB -