Submission #349317

#	Time	Username	Problem	Language	Result	Execution time	Memory
349317		AmirrezaM	Bosses (BOI16_bosses)	C++14	100 / 100	860 ms	748 KiB

bosses

#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 (stderr)

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 / 22
• Subtask 2: 45 / 45
• Subtask 3: 33 / 33