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
5 2 4 6 3 1
3 2 5 3
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
2 1 7
2 2 3
2 3 1
2 9 5
4 5 7 4 8
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
1 9
1 10
2 9 5
1 10
2 6 7
2 3 9
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
1 2
3 3 5 4
2 6 1
2 5 6
2 3 8
2 3 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
2 8 1
1 10
2 5 9
3 5 10 4
2 5 4
2 3 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
2 80 20
1 36
1 87
1 55
1 53
1 48
2 71 57
1 53
1 89
2 71 97
1 72
1 80
1 2
1 8
1 7
...
view   save

correct output
527
view   save

user output
(empty)
view   save

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
5 40 23 17 11 50
3 27 37 30
2 42 36
5 42 43 7 44 17
4 37 36 42 47
5 16 23 41 2 47
2 16 38
2 50 42
2 7 3
3 45 1 5
2 21 7
6 1 28 22 25 31 50
6 12 9 23 36 42 49
2 50 24
3 47 6 26
...
view   save

correct output
156
view   save

user output
(empty)
view   save

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
7 18 16 10 9 29 11 6
6 27 1 2 26 24 10
7 4 22 9 13 24 26 15
7 6 17 2 26 9 13 7
7 28 19 8 13 21 12 14
10 29 28 14 3 12 15 21 19 26 2
4 6 8 30 24
7 20 18 17 24 15 19 30
5 23 12 10 30 11
10 19 5 27 26 4 2 22 16 29 21
5 17 12 29 9 4
8 8 12 13 2 6 26 4 11
7 25 9 5 6 14 16 21
6 27 2 24 3 29 7
7 2 17 10 8 29 23 24
...
view   save

correct output
77
view   save

user output
(empty)
view   save

Test 10

Group: 2

Verdict: TIME LIMIT EXCEEDED

input
100
2 2 77
3 99 94 85
2 47 29
2 33 74
2 73 71
3 27 51 33
4 32 23 36 65
2 42 75
1 20
2 50 44
1 23
3 40 92 7
2 49 30
2 90 61
3 97 56 79
1 70
1 69
2 36 87
2 60 49
...
view   save

correct output
428
view   save

user output
(empty)
view   save

Test 11

Group: 2

Verdict: TIME LIMIT EXCEEDED

input
100
3 50 11 85
2 84 69
2 41 39
2 43 82
2 49 26
2 48 47
2 36 65
2 37 41
2 73 100
1 40
2 20 98
2 46 31
2 29 22
2 99 52
2 50 27
1 45
2 28 44
2 83 60
3 76 93 35
...
view   save

correct output
617
view   save

user output
(empty)
view   save

Test 12

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
200
46 154 36 47 187 86 48 66 124 ...
45 61 110 183 130 18 42 85 22 ...
45 136 145 64 156 194 65 9 187...
52 98 120 24 148 16 190 2 113 ...
52 67 84 188 172 108 10 7 52 7...
58 53 136 71 106 9 166 128 161...
view   save

correct output
531
view   save

user output
(empty)
view   save

Test 13

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
150
60 32 101 42 139 95 36 81 83 1...
70 74 28 136 107 85 104 139 10...
63 118 41 22 51 114 62 99 75 9...
71 116 114 87 7 124 8 18 126 5...
77 41 120 15 119 101 131 2 63 ...
view   save

correct output
370
view   save

user output
(empty)
view   save

Test 14

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
5000
1 3355
1 2176
1 3754
1 950
1 2514
1 2598
1 955
1 2735
1 546
1 3193
1 2008
1 3763
1 1171
1 4015
1 1424
1 859
1 4265
1 1200
1 1397
...
view   save

correct output
6256017
view   save

user output
(empty)
view   save

Test 15

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
5000
1 848
1 418
1 3390
1 2840
1 1464
1 106
1 3795
1 4837
1 3225
1 556
1 4411
1 2678
1 3184
1 744
1 2304
1 4071
1 3934
1 811
1 360
...
view   save

correct output
45193
view   save

user output
(empty)
view   save

Test 16

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
5000
2 4629 753
1 345
3 3573 1802 449
1 3051
1 2745
2 2333 2911
2 3664 2234
6 4402 1966 4982 4955 4557 269...
1 4071
1 4183
2 4421 870
3 3749 1090 1640
2 347 1236
1 4488
1 780
2 1480 2770
2 247 4404
2 3763 2300
2 3697 63
...
view   save

correct output
27449
view   save

user output
(empty)
view   save

Test 17

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
5000
2 2282 1819
2 2987 3194
2 3472 4256
2 3226 3684
2 1921 4023
2 982 1339
2 3481 4918
2 4211 780
2 2932 467
2 2390 2524
2 1175 3682
2 1220 2122
2 531 3107
2 1502 531
2 675 3932
2 3434 2432
2 263 3111
2 2983 2160
2 2633 1673
...
view   save

correct output
39850
view   save

user output
(empty)
view   save

Test 18

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
5000
2 1912 3423
2 419 4226
2 1627 4693
2 4760 1391
2 1488 4966
2 1117 4090
2 2368 3020
2 1123 3506
2 3614 802
2 772 3446
2 4164 3509
2 4268 4545
2 1867 2929
2 2463 220
2 1444 4294
2 611 1472
2 4700 863
2 3815 3713
2 746 1602
...
view   save

correct output
40097
view   save

user output
(empty)
view   save