Submission #838881

#	Time	Username	Problem	Language	Result	Execution time	Memory
838881		vjudge1	Bosses (BOI16_bosses)	C++17	100 / 100	421 ms	3240 KiB

bosses

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,abm,mmx,avx,tune=native")
//#include <algorithm>
#include <bits/stdc++.h>
//#include <cmath>
//#include <iostream>
//#include <vector>
//#include <map>
//#include <set>
//#include <deque>
//#include<stack>
//#include<string>
//#include<string.h>
//#include<set>
//#include<map>
//#include<bitset>
//#include<stdlib.h>
//#include<cassert>
//#include<time.h>
//#include<bitset>

using namespace std;

#define pb push_back
#define sz size()
#define ff first
#define ss second
#define ull unsigned long long
#define all(x) x.begin(), x.end()
#define Resh cin>>tt;while(tt--)so();
#define freopen(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);
#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define ll int

const long long n6 = 1e6+5;
const long long n5 = 1e5+5;
const long long inf = 1e9+10;
const long long mod = 1e9;
const string alp = "abcdefghijklmnopqrstuvwxyz";
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

//--------------------------------------------------------------------------
int a[n5];
int n;
vector<int> V[n5];
queue<int> qu;

ll bfs(int r) {
	ll res = 0;
	for(int i = 0;i <= n5;i++) {
        a[i] = 0;
	}
	qu.push(r);
	a[r] = 1;
	while(!qu.empty()) {
		int u = qu.front();
		qu.pop();
		res += a[u];
		for(int v : V[u]) {
			if(a[v]) continue;
			a[v] = a[u] + 1;
			qu.push(v);
		}
	}
	for(int i = 1;i <= n;i++) {
		if(!a[i]) return inf;
	}
	return res;
}

main() {
    fast
	cin >> n;
	for(int i = 1;i <= n;i++) {
		int k;
		cin >> k;
		for(int j = 0;j < k;j++) {
			int v;
			cin >> v;
			V[v].pb(i);
		}
	}
	ll ans = inf;
	for(int i = 1;i <= n;i++) {
        ans = min(ans, bfs(i));
	}
	cout << ans;
}

Compilation message (stderr)

bosses.cpp:73:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   73 | main() {
      | ^~~~
bosses.cpp: In function 'int bfs(int)':
bosses.cpp:53:14: warning: iteration 100005 invokes undefined behavior [-Waggressive-loop-optimizations]
   53 |         a[i] = 0;
      |         ~~~~~^~~
bosses.cpp:52:18: note: within this loop
   52 |  for(int i = 0;i <= n5;i++) {
      |                ~~^~~~~
bosses.cpp:53:14: warning: 'void* __builtin_memset(void*, int, long unsigned int)' forming offset [400020, 400023] is out of the bounds [0, 400020] of object 'a' with type 'int [100005]' [-Warray-bounds]
   53 |         a[i] = 0;
      |         ~~~~~^~~
bosses.cpp:45:5: note: 'a' declared here
   45 | int a[n5];
      |     ^

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