oj.uz

Submission #100378

# Submission time Handle Problem Language Result Execution time Memory
100378 2019-03-10T17:48:31 Z shafinalam Bosses (BOI16_bosses) C++14
100 / 100
 589 ms 760 KB 
#include <bits/stdc++.h>

using namespace std;

const int mx = 1e5+5;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef pair<int,int>pii;
typedef pair<int,pii>piii;

#define  sf scanf
#define  pf printf

#define  input freopen("input.txt","r",stdin)
#define  output freopen("output.txt","w",stdout)

#define  inf 1e16
#define  ff first
#define  ss second
#define  MP make_pair
#define  pb push_back
#define  all(v) v.begin(), v.end()
#define  printcase(cases) printf("Case %d:", cases);
#define  Unique(a) a.erase(unique(a.begin(),a.end()),a.end())
#define  FAST  ios_base::sync_with_stdio(0);cout.tie(0)
#define  endl printf("\n")
#define  __lcm(a, b) ((a*b)/__gcd(a, b))

int  Set(int N,int pos)
{
    return N=N | (1<<pos);
}
int  reset(int N,int pos)
{
    return N= N & ~(1<<pos);
}
bool check(int N,int pos)
{
    return (bool)(N & (1<<pos));
}

int dis[5005];
int n;
vector<int> adj[5005];

int bfs(int s)
{
    memset(dis, -1, sizeof dis);
    dis[s] = 1;
    queue<int>q;
    q.push(s);
    while(!q.empty())
    {
        s = q.front();
        q.pop();
        for(auto i : adj[s])
        {
            if(dis[i] != -1) continue;
            dis[i] = dis[s] + 1;
            q.push(i);
        }
    }
    int ret = 0;
    for(int i=1; i<=n; i++)
    {
        if(dis[i] == -1) return -1;
        ret += dis[i];
    }
    return ret;
}
int main()
{
    sf("%d", &n);
    for(int i = 1; i <= n; i++)
    {
        int k;
        scanf("%d", &k);
        while(k--)
        {
            int x;
            sf("%d", &x);
            adj[x].push_back(i);
        }
    }
    int ans = INT_MAX;
    for(int i = 1; i <= n; i++)
    {
        int x = bfs(i);
        if(x == -1) continue;
        ans = min(ans, x);
    }
    pf("%d\n", ans);
    return 0;
}

Compilation message

bosses.cpp: In function 'int main()':
bosses.cpp:74:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     sf("%d", &n);
       ^
bosses.cpp:78:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &k);
         ~~~~~^~~~~~~~~~
bosses.cpp:82:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             sf("%d", &x);
               ^

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 6 ms 512 KB Output is correct
13 Correct 5 ms 512 KB Output is correct
14 Correct 103 ms 580 KB Output is correct
15 Correct 6 ms 512 KB Output is correct
16 Correct 589 ms 664 KB Output is correct
17 Correct 539 ms 640 KB Output is correct
18 Correct 523 ms 760 KB Output is correct