oj.uz

Submission #349317

# Submission time Handle Problem Language Result Execution time Memory
349317 2021-01-17T12:01:50 Z AmirrezaM Bosses (BOI16_bosses) C++14
100 / 100
 860 ms 748 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<pii,int> ppiii;

// vectors and Sets:
#define vc vector
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define it iterator
#define SZ(x) (ll)((x).size())
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rend(), (c).rbegin

// pairs
#define mp make_pair
#define fr first
#define sc second

// loops
#define FOR(i , m , n) for(int (i) = (m) ; (i) < (n) ; (i)++)
#define ROF(i , n , m) for(int (i) = (n) ; (i) >= (m) ; (i)--)
//#define FOR(n) for(int (i) = (o) ; (i) < (n) ; (i)++)
//#define ROF(n) for(int (i) = (m) ; (i) >= (0) ; (i)--)

// useful numbers
#define INF ((1 << 64) - 1)
#define BPT(n) pow(2,floor(log2((n))));
#define LPT(n) pow(2,ceil(log2((n))*1.0));

// execution time check and Debug
#define StartEX; clock_t startExeTime = clock();
#define EndEX; clock_t endExeTime = clock();
#define ExTime; cerr << "\nTotal Execution Time is: " << double(-double(startExeTime)+double(endExeTime)) / CLOCKS_PER_SEC;
#define debug(x) cerr << #x << " : " << x << '\n'
#define endl "\n"

// time optimization
#define Heh ios::sync_with_stdio(false);cin.tie(0);
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O0")
#pragma GCC optimize("O1")

//Calculates b'th power of a
ll pw(int a,int b){
    ll ret = 1;
    ll mul = a;
    while(b > 0){
        if(b&1)
            ret *= mul;
        mul *= mul;
        b /= 2;
    }
    return ret;
}

//Converts s string to int
ll to_int(string s){
    ll ret = 0;
    FOR(i,0,s.size()){
        ret += pw(10,s.size()-i-1) * (ll)(s[i] - '0');
    }
    return ret;
}
const int MAXN = 5e3 + 53;
int n , dis[MAXN];
bool mark[MAXN];
vc<int> adj[MAXN];
queue<int> Q;
int main()
{
    int n;
    cin >> n;
    FOR(i,0,n){
        int k;
        cin >> k;
        FOR(j,0,k){
            int e;
            cin >> e;
            e--;
            adj[e].pb(i);
        }
    }
    int ans = 1e9;
    FOR(st,0,n){
        FOR(i,0,n) mark[i] = 0, dis[i] = 1e9;
        dis[st] = 1 , Q.push(st);
        int cost = 0;
        while(Q.size()){
            int v = Q.front(); Q.pop(); mark[v] = 1;
            FOR(i,0,adj[v].size()){
                int to = adj[v][i];
                if(!mark[to]){
                    mark[to] = 1;
                    dis[to] = dis[v] + 1;
                    Q.push(to);
                }
            }
        }
        FOR(i,0,n){
            if(dis[i] > n + 2){
                cost = 1e9;
                break;
            }
            cost += dis[i];
        }
        ans = min(ans , cost);
    }
    cout << ans << endl;
    // Doesn't Ac? Read the Bottom :/
}

// stuff you should look for(Thanks Benq)
//	*** int overflow, array bounds
//	* special cases (n=1?)
//	**** do smth instead of nothing and stay organized
//	* WRITE STUFF DOWN
//	*** DON'T GET STUCK ON ONE APPROACH

Compilation message

bosses.cpp:37:9: warning: ISO C++11 requires whitespace after the macro name
   37 | #define StartEX; clock_t startExeTime = clock();
      |         ^~~~~~~
bosses.cpp:38:9: warning: ISO C++11 requires whitespace after the macro name
   38 | #define EndEX; clock_t endExeTime = clock();
      |         ^~~~~
bosses.cpp:39:9: warning: ISO C++11 requires whitespace after the macro name
   39 | #define ExTime; cerr << "\nTotal Execution Time is: " << double(-double(startExeTime)+double(endExeTime)) / CLOCKS_PER_SEC;
      |         ^~~~~~
bosses.cpp: In function 'll to_int(std::string)':
bosses.cpp:26:32: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i , m , n) for(int (i) = (m) ; (i) < (n) ; (i)++)
      |                                ^
bosses.cpp:66:5: note: in expansion of macro 'FOR'
   66 |     FOR(i,0,s.size()){
      |     ^~~
bosses.cpp:26:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 | #define FOR(i , m , n) for(int (i) = (m) ; (i) < (n) ; (i)++)
      |                                            ~~~~^~~~~
bosses.cpp:66:5: note: in expansion of macro 'FOR'
   66 |     FOR(i,0,s.size()){
      |     ^~~
bosses.cpp: In function 'int main()':
bosses.cpp:26:32: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i , m , n) for(int (i) = (m) ; (i) < (n) ; (i)++)
      |                                ^
bosses.cpp:80:5: note: in expansion of macro 'FOR'
   80 |     FOR(i,0,n){
      |     ^~~
bosses.cpp:26:32: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   26 | #define FOR(i , m , n) for(int (i) = (m) ; (i) < (n) ; (i)++)
      |                                ^
bosses.cpp:83:9: note: in expansion of macro 'FOR'
   83 |         FOR(j,0,k){
      |         ^~~
bosses.cpp:26:32: warning: unnecessary parentheses in declaration of 'st' [-Wparentheses]
   26 | #define FOR(i , m , n) for(int (i) = (m) ; (i) < (n) ; (i)++)
      |                                ^
bosses.cpp:91:5: note: in expansion of macro 'FOR'
   91 |     FOR(st,0,n){
      |     ^~~
bosses.cpp:26:32: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i , m , n) for(int (i) = (m) ; (i) < (n) ; (i)++)
      |                                ^
bosses.cpp:92:9: note: in expansion of macro 'FOR'
   92 |         FOR(i,0,n) mark[i] = 0, dis[i] = 1e9;
      |         ^~~
bosses.cpp:26:32: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i , m , n) for(int (i) = (m) ; (i) < (n) ; (i)++)
      |                                ^
bosses.cpp:97:13: note: in expansion of macro 'FOR'
   97 |             FOR(i,0,adj[v].size()){
      |             ^~~
bosses.cpp:26:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 | #define FOR(i , m , n) for(int (i) = (m) ; (i) < (n) ; (i)++)
      |                                            ~~~~^~~~~
bosses.cpp:97:13: note: in expansion of macro 'FOR'
   97 |             FOR(i,0,adj[v].size()){
      |             ^~~
bosses.cpp:26:32: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i , m , n) for(int (i) = (m) ; (i) < (n) ; (i)++)
      |                                ^
bosses.cpp:106:9: note: in expansion of macro 'FOR'
  106 |         FOR(i,0,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 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 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 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 7 ms 620 KB Output is correct
13 Correct 5 ms 492 KB Output is correct
14 Correct 213 ms 492 KB Output is correct
15 Correct 44 ms 512 KB Output is correct
16 Correct 720 ms 748 KB Output is correct
17 Correct 860 ms 676 KB Output is correct
18 Correct 856 ms 620 KB Output is correct