oj.uz

Submission #838881

# Submission time Handle Problem Language Result Execution time Memory
838881 2023-08-28T04:51:42 Z vjudge1 Bosses (BOI16_bosses) C++17
100 / 100
 421 ms 3240 KB 
#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

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.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3028 KB Output is correct
2 Correct 2 ms 3028 KB Output is correct
3 Correct 2 ms 3028 KB Output is correct
4 Correct 2 ms 3028 KB Output is correct
5 Correct 2 ms 3152 KB Output is correct
6 Correct 2 ms 3028 KB Output is correct
7 Correct 2 ms 3028 KB Output is correct
8 Correct 2 ms 3028 KB Output is correct
9 Correct 3 ms 3028 KB Output is correct
10 Correct 3 ms 3028 KB Output is correct
11 Correct 2 ms 3028 KB Output is correct
12 Correct 5 ms 3156 KB Output is correct
13 Correct 5 ms 3156 KB Output is correct
14 Correct 100 ms 3156 KB Output is correct
15 Correct 25 ms 3156 KB Output is correct
16 Correct 421 ms 3240 KB Output is correct
17 Correct 418 ms 3156 KB Output is correct
18 Correct 415 ms 3156 KB Output is correct