oj.uz

Submission #332103

# Submission time Handle Problem Language Result Execution time Memory
332103 2020-12-01T12:53:03 Z iliccmarko Bosses (BOI16_bosses) C++14
100 / 100
 962 ms 748 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
#define INF 1000000000
#define LINF 1000000000000000LL
#define pb push_back
#define all(x) x.begin(), x.end()
#define len(s) (int)s.size()
#define test_case { int t; cin>>t; while(t--)solve(); }
#define input(n, v) {for(int i = 0;i<n;i++) cin>>v[i];}
#define output(n, v) {for(int i = 0;i<n;i++) cout<<v[i]<<" "; cout<<endl;}
#define single_case solve();
#define line cout<<"------------"<<endl;
#define ios { ios_base::sync_with_stdio(false); cin.tie(NULL); }
using namespace std;
int n;
const int N = 5e3 + 5;
vector<vector<int> > v(N);
bitset<N> vidjen;
int dp[N];


int make_graph(int u)
{
    for(int i = 0;i<n;i++)
        vidjen[i] = 0;
    queue<pair<int, int > > q;
    q.push({u, 0});
    vidjen[u] = 1;
    int cnt = 0;
    int w = 0;
    while(len(q))
    {
        int top = q.front().first;
        int lvl = q.front().second;
        cnt += 1+lvl;
        q.pop();
        w++;
        for(int x : v[top])
        {
            if(vidjen[x]) continue;
            q.push({x, lvl+1});
            vidjen[x] = 1;
        }
    }
    if(w==n) return cnt;
    else return INF;

}

int main()
{
    //ios
    scanf("%d", &n);
    for(int i = 0;i<n;i++)
    {
        int k;
        cin>>k;
        while(k--)
        {
            int a;
            cin>>a;
            a--;
            v[a].pb(i);
        }
    }
    int res = INF;
    int root;
    int mini = INF;
    for(int i = 0;i<n;i++)
    {
        res = min(res, make_graph(i));
    }

    

    printf("%d", res);





    return 0;
}

Compilation message

bosses.cpp: In function 'int main()':
bosses.cpp:69:9: warning: unused variable 'root' [-Wunused-variable]
   69 |     int root;
      |         ^~~~
bosses.cpp:70:9: warning: unused variable 'mini' [-Wunused-variable]
   70 |     int mini = INF;
      |         ^~~~
bosses.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   55 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 504 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 2 ms 492 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 504 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 2 ms 492 KB Output is correct
12 Correct 10 ms 620 KB Output is correct
13 Correct 6 ms 748 KB Output is correct
14 Correct 262 ms 612 KB Output is correct
15 Correct 74 ms 748 KB Output is correct
16 Correct 792 ms 620 KB Output is correct
17 Correct 918 ms 720 KB Output is correct
18 Correct 962 ms 720 KB Output is correct