oj.uz

답안 #53060

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
53060 2018-06-28T00:13:38 Z andremfq Bosses (BOI16_bosses) C++17
100 / 100
 851 ms 1484 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <limits.h>
#include <math.h>
#include <time.h>
#include <iostream>
#include <functional>
#include <numeric>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <string>
#include <bitset>
#include <map>
#include <set>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;

int n;
vector<int> gph[5005];

bool vis[5005];
int sz[5005];
int par[5005];

vector<int> ord;

lint solve(int r){
	memset(vis, 0, sizeof(vis));
	memset(sz, 0, sizeof(sz));
	ord.clear();
	queue<int> que;
	que.push(r);
	vis[r] = 1;
	while(!que.empty()){
		int x = que.front();
		que.pop();
		ord.push_back(x);
		for(auto &i : gph[x]){
			if(!vis[i]){
				vis[i] = 1; 
				que.push(i);
				par[i] = x;
			}
		}
	}
	if(ord.size() != n) return 1e18;
	lint ret = 0;
	for(int i=ord.size()-1; i>=0; i--){
		sz[ord[i]]++;
		ret += sz[ord[i]];
		if(ord[i] != r){
			sz[par[ord[i]]] += sz[ord[i]];
		}
	}
	return ret;
}

int main(){
	scanf("%d",&n);
	for(int i=1; i<=n; i++){
		int t;
		scanf("%d",&t);
		for(int j=0; j<t; j++){
			int p;
			scanf("%d",&p);
			gph[p].push_back(i);
		}
	}
	lint ret = 1e18;
	for(int i=1; i<=n; i++){
		ret = min(ret, solve(i));
	}
	cout << ret;
}

Compilation message

bosses.cpp: In function 'lint solve(int)':
bosses.cpp:53:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(ord.size() != n) return 1e18;
     ~~~~~~~~~~~^~~~
bosses.cpp: In function 'int main()':
bosses.cpp:66:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
bosses.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&t);
   ~~~~~^~~~~~~~~
bosses.cpp:72:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&p);
    ~~~~~^~~~~~~~~

Subtask #1
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 2 ms 656 KB Output is correct
4 Correct 2 ms 656 KB Output is correct
5 Correct 2 ms 720 KB Output is correct
6 Correct 2 ms 720 KB Output is correct

Subtask #2
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 2 ms 656 KB Output is correct
4 Correct 2 ms 656 KB Output is correct
5 Correct 2 ms 720 KB Output is correct
6 Correct 2 ms 720 KB Output is correct
7 Correct 2 ms 720 KB Output is correct
8 Correct 2 ms 820 KB Output is correct
9 Correct 25 ms 820 KB Output is correct
10 Correct 3 ms 932 KB Output is correct
11 Correct 4 ms 940 KB Output is correct

Subtask #3
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 2 ms 656 KB Output is correct
4 Correct 2 ms 656 KB Output is correct
5 Correct 2 ms 720 KB Output is correct
6 Correct 2 ms 720 KB Output is correct
7 Correct 2 ms 720 KB Output is correct
8 Correct 2 ms 820 KB Output is correct
9 Correct 25 ms 820 KB Output is correct
10 Correct 3 ms 932 KB Output is correct
11 Correct 4 ms 940 KB Output is correct
12 Correct 7 ms 976 KB Output is correct
13 Correct 6 ms 1052 KB Output is correct
14 Correct 155 ms 1176 KB Output is correct
15 Correct 7 ms 1176 KB Output is correct
16 Correct 672 ms 1320 KB Output is correct
17 Correct 851 ms 1428 KB Output is correct
18 Correct 818 ms 1484 KB Output is correct