Code Submission Evaluation System Login

BOI 2016, day 1

Start:2016-05-12 09:00:00
End:2016-05-12 14:00:00
 

Tasks | Scoreboard | Statistics


CSES - BOI 2016, day 1 - Results
History
2016-05-12 15:16:47100
2016-05-12 12:59:590
2016-05-12 11:58:080
2016-05-12 10:56:180
2016-05-12 10:55:370
2016-05-12 10:52:420
2016-05-12 10:49:120
2016-05-12 09:57:050
Task:Bosses
Sender:terz99
Submission time:2016-05-12 12:59:59
Language:C++
Status:READY
Score:0

Feedback

groupverdictscore
#1WRONG ANSWER0
#2TIME LIMIT EXCEEDED0
#3TIME LIMIT EXCEEDED0

Test results

testverdicttime (s)group
#1ACCEPTED0.06 / 1.501details
#2ACCEPTED0.05 / 1.501details
#3WRONG ANSWER0.06 / 1.501details
#4WRONG ANSWER0.06 / 1.501details
#5WRONG ANSWER0.06 / 1.501details
#6WRONG ANSWER0.05 / 1.501details
#7TIME LIMIT EXCEEDED-- / 1.502details
#8TIME LIMIT EXCEEDED-- / 1.502details
#9TIME LIMIT EXCEEDED-- / 1.502details
#10TIME LIMIT EXCEEDED-- / 1.502details
#11TIME LIMIT EXCEEDED-- / 1.502details
#12TIME LIMIT EXCEEDED-- / 1.503details
#13TIME LIMIT EXCEEDED-- / 1.503details
#14TIME LIMIT EXCEEDED-- / 1.503details
#15TIME LIMIT EXCEEDED-- / 1.503details
#16TIME LIMIT EXCEEDED-- / 1.503details
#17TIME LIMIT EXCEEDED-- / 1.503details
#18TIME LIMIT EXCEEDED-- / 1.503details

Compiler report

input/code.cpp: In function 'void DFS(int)':
input/code.cpp:43:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < tree[x].size(); i++){
                                  ^
input/code.cpp: In function 'void solve(int, int, int)':
input/code.cpp:63:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < mat[x].size(); i++){
                                 ^

Code

#include <bits/stdc++.h>
using namespace std;

#define IO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl "\n"
#define INF 2147483647
#define DBG 666
#define mp make_pair
#define revsort(x,y) sort((x),(x+y));reverse((x),(x+y));

typedef long long ll;

int n, cnt[5005], result = INF;
vector< vector<int> > mat, tree;
bool vis[5005];

void init(){

	cin >> n;

	mat.resize(n, vector<int>());

	for(int i = 0; i < n; i++){

		int m;
		cin >> m;
		for(int j = 0; j < m; j++){

			int tmp;
			cin >> tmp;
			tmp--;
			mat[tmp].push_back(i);
		}
	}
}

void DFS(int x){

	if(tree[x].size() == 0){
		cnt[x] = 1;
		return;
	}
	for(int i = 0; i < tree[x].size(); i++){
		DFS(tree[x][i]);
		cnt[x] += cnt[tree[x][i]];
	}
	cnt[x]++;
}

void solve(int root, int x, int size){

	if(size == n){

		memset(cnt, 0, sizeof(cnt));
		DFS(root);
		int ans = 0;
		for(int i = 0; i < n; i++)
			ans += cnt[i];
		result = min(result, ans);
		return;
	}

	for(int i = 0; i < mat[x].size(); i++){

		int next = mat[x][i];
		if(vis[next])
			continue;

		vis[next] = true;
		tree[x].push_back(next);
		solve(root, next, size+1);
		solve(root, x, size+1);
		vis[next] = false;
		tree[x].pop_back();
	}
}

void solve(){

	memset(vis, false, sizeof(vis));
	tree.resize(n, vector<int>());
	for(int i = 0; i < n; i++){
		vis[i] = true;
		solve(i, i, 1);
		vis[i] = false;
	}
	cout << result << endl;
}

int main(){

	IO;
	init();
	solve();
	return 0;
}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
4
1 4
3 1 3 4
2 1 2
1 3
view   save

correct output
8

view   save

user output
8

view   save

Test 2

Group: 1

Verdict: ACCEPTED

input
6
2 6 5
3 4 6 3
2 4 1
4 5 3 1 6
...
view   save

correct output
12

view   save

user output
12

view   save

Test 3

Group: 1

Verdict: WRONG ANSWER

input
9
2 6 3
2 8 4
0
4 8 3 6 9
...
view   save

correct output
22

view   save

user output
24

view   save

Test 4

Group: 1

Verdict: WRONG ANSWER

input
10
3 3 2 8
3 6 7 3
4 6 10 7 9
1 10
...
view   save

correct output
24

view   save

user output
27

view   save

Test 5

Group: 1

Verdict: WRONG ANSWER

input
10
3 4 8 10
1 10
1 5
3 6 8 5
...
view   save

correct output
23

view   save

user output
28

view   save

Test 6

Group: 1

Verdict: WRONG ANSWER

input
10
2 2 6
2 3 5
2 4 1
2 6 7
...
view   save

correct output
26

view   save

user output
30

view   save

Test 7

Group: 2

Verdict: TIME LIMIT EXCEEDED

input
100
2 78 92
1 15
1 57
1 45
...
view   save

correct output
527

view   save

user output
(empty)

Test 8

Group: 2

Verdict: TIME LIMIT EXCEEDED

input
50
6 16 31 50 6 4 8
7 7 16 27 22 15 30 14
5 20 22 42 33 37
3 18 45 9
...
view   save

correct output
156

view   save

user output
(empty)

Test 9

Group: 2

Verdict: TIME LIMIT EXCEEDED

input
30
5 12 26 25 18 24
8 6 13 5 7 10 22 20 29
6 16 14 9 27 5 20
3 19 17 11
...
view   save

correct output
77

view   save

user output
(empty)

Test 10

Group: 2

Verdict: TIME LIMIT EXCEEDED

input
100
2 2 77
3 99 94 85
2 47 29
2 33 74
...
view   save

correct output
428

view   save

user output
(empty)

Test 11

Group: 2

Verdict: TIME LIMIT EXCEEDED

input
100
3 50 11 85
2 84 69
2 41 39
2 43 82
...
view   save

correct output
617

view   save

user output
(empty)

Test 12

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
200
46 154 36 47 187 86 48 66 124 ...
view   save

correct output
531

view   save

user output
(empty)

Test 13

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
150
60 32 101 42 139 95 36 81 83 1...
view   save

correct output
370

view   save

user output
(empty)

Test 14

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
5000
1 3355
1 2176
1 3754
1 950
...
view   save

correct output
6256017

view   save

user output
(empty)

Test 15

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
5000
1 848
1 418
1 3390
1 2840
...
view   save

correct output
45193

view   save

user output
(empty)

Test 16

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
5000
2 4629 753
1 345
3 3573 1802 449
1 3051
...
view   save

correct output
27449

view   save

user output
(empty)

Test 17

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
5000
2 2282 1819
2 2987 3194
2 3472 4256
2 3226 3684
...
view   save

correct output
39850

view   save

user output
(empty)

Test 18

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
5000
2 1912 3423
2 419 4226
2 1627 4693
2 4760 1391
...
view   save

correct output
40097

view   save

user output
(empty)