oj.uz

Submission #368050

# Submission time Handle Problem Language Result Execution time Memory
368050 2021-02-19T11:53:19 Z mario05092929 Bosses (BOI16_bosses) C++11
100 / 100
 773 ms 876 KB 
#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define all(v) v.begin(),v.end()
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast") 
#pragma gcc optimize("unroll-loops")
using namespace std;
const int INF = 1e9;
const int TMX = 1 << 18;
const long long llINF = 1e16;
const long long mod = 1e9+7;
const long long hashmod = 100003;
const int MAXN = 100000;
const int MAXM = 1000000;
typedef long long ll;
typedef long double ld;
typedef pair <int,int> pi;
typedef pair <ll,ll> pl;
typedef vector <int> vec;
typedef vector <pi> vecpi;
typedef long long ll;
int n,dep[5005],c[5005];
vec v[5005];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n;
	for(int i = 1;i <= n;i++) {
		int cn; cin >> cn;
		while(cn--) {
			int x; cin >> x;
			v[x].pb(i);
		}
	}
	int rans = INF;
	for(int st = 1;st <= n;st++) {
		memset(c,0,sizeof(c));
		queue <int> q;
		q.push(st);
		dep[st] = 1;
		c[st] = 1;
		int ans = 1,cn = 0;
		while(!q.empty()) {
			int x = q.front(); q.pop();
			cn++;
			for(int i : v[x]) {
				if(c[i]) continue;
				dep[i] = dep[x]+1;
				ans += dep[i];
				c[i] = 1;
				q.push(i);
			}
		}
		if(cn == n) rans = min(rans,ans);
	}
	cout << rans;
}

Compilation message

bosses.cpp:6: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
    6 | #pragma gcc optimize("O3")
      | 
bosses.cpp:7: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
    7 | #pragma gcc optimize("Ofast")
      | 
bosses.cpp:8: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
    8 | #pragma gcc optimize("unroll-loops")
      |

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 5 ms 620 KB Output is correct
13 Correct 4 ms 620 KB Output is correct
14 Correct 140 ms 620 KB Output is correct
15 Correct 7 ms 640 KB Output is correct
16 Correct 577 ms 876 KB Output is correct
17 Correct 723 ms 832 KB Output is correct
18 Correct 773 ms 876 KB Output is correct