oj.uz

Submission #735642

# Submission time Handle Problem Language Result Execution time Memory
735642 2023-05-04T12:28:38 Z MODDI Bosses (BOI16_bosses) C++14
100 / 100
 634 ms 764 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<long long> vl;
typedef vector<int> vi;
int n;
vi G[5100];
vector<pii> ord;
ll rez = 0, all = 0;
bool vis[5100];
void bfs(int v, int br)
{
    if(vis[v] and br!=ord.size()){bfs(ord[br].first, br+1); return;}
    else if(vis[v] and br==ord.size())return;
    vis[v]=true;
    all++;
    if(br==0)rez+=1;
    else rez+=ord[br-1].second;
    for(auto next : G[v])
    {
        if(!vis[next] and br!=0){ord.push_back({next, ord[br-1].second+1});}
        else if (!vis[next] and br==0)ord.push_back({next, 2});
    }
    if(br==ord.size())return;
 
    bfs(ord[br].first, br+1);
}
int main(){
	cin>>n;
	for(int i = 0; i < n; i++){
		int k;
		cin>>k;
		for(int j = 0; j < k; j++){
			int a;
			cin>>a;
			a--;
			G[a].pb(i);
		}
	}
	ll ans = 1e9;
	for(int i = 0; i < n; i++){
		rez = 0;
		all = 0;
		memset(vis, false, sizeof vis);
		ord.clear();
		bfs(i, 0);
//		cout<<rez<<endl;
		if(all==n)	ans = min(ans, rez);
	}
	cout<<ans<<endl;
	return 0;
}

Compilation message

bosses.cpp: In function 'void bfs(int, int)':
bosses.cpp:17:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     if(vis[v] and br!=ord.size()){bfs(ord[br].first, br+1); return;}
      |                   ~~^~~~~~~~~~~~
bosses.cpp:18:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     else if(vis[v] and br==ord.size())return;
      |                        ~~^~~~~~~~~~~~
bosses.cpp:28:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     if(br==ord.size())return;
      |        ~~^~~~~~~~~~~~

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 3 ms 432 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 16 ms 596 KB Output is correct
13 Correct 16 ms 596 KB Output is correct
14 Correct 178 ms 596 KB Output is correct
15 Correct 4 ms 596 KB Output is correct
16 Correct 552 ms 660 KB Output is correct
17 Correct 634 ms 764 KB Output is correct
18 Correct 632 ms 764 KB Output is correct