Submission #679799

#	Time	Username	Problem	Language	Result	Execution time	Memory
679799		ByeWorld	Bosses (BOI16_bosses)	C++17	100 / 100	1173 ms	98736 KiB

bosses

#include <bits/stdc++.h>
#pragma GCC optimize("01")
//#define int long long
#define ll long long
#define fi first
#define se second
#define pb push_back
using namespace std;
const int MAXN = 5e3+10;
const int MAXA = 4e4+10;
const int LOG = 20;
const int VOD = 0;
const int MOD = 1e9+7;
const int MODD = 1e9+6;
const ll INF = 2e18;
typedef pair<int,int> pii;
typedef pair<pii,pii> ipii;

int k[MAXN];
vector <int> adj[MAXN];
int dis[MAXN][MAXN];//dari j ke i, i <- j
queue <pii> q;

void bfs(int sta, int DIS){
	q.push({sta, DIS});
	while(!q.empty()){
		int nw = q.front().fi; int dist = q.front().se;
		q.pop();
		if(dis[nw][sta] != -1) continue;
		dis[nw][sta] = dist;
		for(auto nx : adj[nw]){
			q.push({nx, dist+1});
		}
	}
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n; scanf("%d", &n);

    for(int i=1; i<=n; i++){
    	for(int j=1; j<=n; j++) dis[i][j] = -1;
    }

    for(int i=1; i<=n; i++){
    	scanf("%d", &k[i]);
    	for(int j=1; j<=k[i]; j++){
    		int to; scanf("%d", &to);
    		adj[i].pb(to);
    	}
    }
    for(int i=1; i<=n; i++){
    	bfs(i, 0);
    }
    /*for(int i=1; i<=n; i++){
    	cout << i << '\n';
    	for(int j=1; j<=n; j++) cout << dis[i][j] << ' ';
    	cout << '\n';
    }*/
    ll ans = INF;
    for(int i=1; i<=n; i++){
    	ll sum = 0; bool b = 1;
    	for(int j=1; j<=n; j++){
    		if(dis[i][j] == -1){b=0; break;}
    		sum += dis[i][j];
    	}
    	if(!b) continue;
    	ans = min(ans, sum);
    	//if(sum == 3) cout << i << '\n';
    }
    printf("%d", ans+n);
    printf("\n");
    return 0;
}

Compilation message (stderr)

bosses.cpp: In function 'int main()':
bosses.cpp:71:14: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
   71 |     printf("%d", ans+n);
      |             ~^   ~~~~~
      |              |      |
      |              int    long long int
      |             %lld
bosses.cpp:39:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |     int n; scanf("%d", &n);
      |            ~~~~~^~~~~~~~~~
bosses.cpp:46:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |      scanf("%d", &k[i]);
      |      ~~~~~^~~~~~~~~~~~~
bosses.cpp:48:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |       int to; scanf("%d", &to);
      |               ~~~~~^~~~~~~~~~~

• Subtask 1: 22 / 22
• Subtask 2: 45 / 45
• Subtask 3: 33 / 33