Submission #788232

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
788232	2023-07-20T02:57:54 Z	mindiyak	Connecting Supertrees (IOI20_supertrees)	C++14	21 / 100	233 ms	22048 KB

supertrees

#include "supertrees.h"
#include <vector>
#include <set>
#include <iostream>

using namespace std;

vector<int> parent(1003);

int find_head(int n){
	if(parent[n] == n){
		return n;
	}return find_head(parent[n]);
}

int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	set<int> heads;
	vector<vector<int>>ans(n,vector<int>(n,0));

	for (int i = 0; i < n; i++) {
		parent[i] = i;
	}

	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(i==j)
				continue;
			if(p[i][j] == 3){
				return 0;
			}else if(p[i][j] == 1){
				int lower = min(i,j);
				int higher = max(i,j);
				if(find_head(lower) != find_head(higher)){
					ans[i][j] = 1;
					ans[j][i] = 1;
					parent[higher] = find_head(lower);
				}
			}else if(p[i][j] == 2){
				if(n < 3){
					return 0;
				}
				heads.insert(find_head(i));
				heads.insert(find_head(j));
			}
		}
	}

	// cout << "table travers" << endl;

	vector<int> header;
	for (int i : heads) {
		header.push_back(i);
	}


	int t = header.size();

	// cout << t << " " << (0<(t-1)) << endl;

	for (int i = 0; i < (t-1); i++) {
		// cout << "for" << endl;
		ans[header[i]][header[i+1]] = 1;
		ans[header[i+1]][header[i]] = 1;
	}
	if(t > 2){
		// cout << "comare" << endl;
		ans[header[0]][header[t-1]] = 1;
		ans[header[t-1]][header[0]] = 1;
	}

	// cout << "headers connected" << endl;

	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			int i_head = find_head(i);
			int j_head = find_head(j);
			if(i==j)
				continue;
			if(p[i][j] == 0){
				if(i_head == j_head){
					return 0;
				}
				if(heads.count(i_head) == 1 and heads.count(j_head) == 1){
					return 0;
				}
			}else if(p[i][j] == 1){
				if(i_head != j_head){
					return 0;
				}
			}else if(p[i][j] == 2){
				if(i_head == j_head){
					return 0;
				}
				if(heads.count(i_head) == 0 or heads.count(j_head) == 0){
					return 0;
				}
			}
		}
	}


	build(ans);
	return 1;
}

Subtask #1
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	6 ms	1168 KB	Output is correct
7	Correct	149 ms	22008 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	6 ms	1168 KB	Output is correct
7	Correct	149 ms	22008 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	6 ms	1108 KB	Output is correct
13	Correct	157 ms	21964 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	3 ms	724 KB	Output is correct
17	Correct	69 ms	12048 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Correct	39 ms	5704 KB	Output is correct
21	Correct	159 ms	21936 KB	Output is correct
22	Correct	165 ms	22020 KB	Output is correct
23	Correct	163 ms	22020 KB	Output is correct
24	Correct	158 ms	22048 KB	Output is correct
25	Correct	65 ms	12048 KB	Output is correct
26	Correct	90 ms	12036 KB	Output is correct
27	Correct	163 ms	21928 KB	Output is correct
28	Correct	151 ms	22036 KB	Output is correct

Subtask #3
0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	6 ms	1164 KB	Output is correct
9	Correct	149 ms	22020 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	9 ms	1172 KB	Output is correct
13	Correct	233 ms	22036 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	1 ms	300 KB	Output is correct
16	Correct	4 ms	852 KB	Output is correct
17	Correct	98 ms	14072 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	0 ms	308 KB	Output is correct
21	Incorrect	16 ms	3788 KB	Answer gives possible 0 while actual possible 1
22	Halted	0 ms	0 KB	-

Subtask #4
0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	38 ms	5684 KB	Output is correct
5	Correct	152 ms	22044 KB	Output is correct
6	Correct	172 ms	21948 KB	Output is correct
7	Correct	157 ms	21984 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Incorrect	15 ms	3212 KB	Answer gives possible 0 while actual possible 1
10	Halted	0 ms	0 KB	-

Subtask #5
0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	6 ms	1168 KB	Output is correct
7	Correct	149 ms	22008 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	6 ms	1108 KB	Output is correct
13	Correct	157 ms	21964 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	3 ms	724 KB	Output is correct
17	Correct	69 ms	12048 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Correct	39 ms	5704 KB	Output is correct
21	Correct	159 ms	21936 KB	Output is correct
22	Correct	165 ms	22020 KB	Output is correct
23	Correct	163 ms	22020 KB	Output is correct
24	Correct	158 ms	22048 KB	Output is correct
25	Correct	65 ms	12048 KB	Output is correct
26	Correct	90 ms	12036 KB	Output is correct
27	Correct	163 ms	21928 KB	Output is correct
28	Correct	151 ms	22036 KB	Output is correct
29	Correct	0 ms	212 KB	Output is correct
30	Correct	1 ms	212 KB	Output is correct
31	Correct	0 ms	212 KB	Output is correct
32	Correct	0 ms	212 KB	Output is correct
33	Correct	0 ms	212 KB	Output is correct
34	Correct	1 ms	212 KB	Output is correct
35	Correct	0 ms	212 KB	Output is correct
36	Correct	6 ms	1164 KB	Output is correct
37	Correct	149 ms	22020 KB	Output is correct
38	Correct	0 ms	212 KB	Output is correct
39	Correct	0 ms	212 KB	Output is correct
40	Correct	9 ms	1172 KB	Output is correct
41	Correct	233 ms	22036 KB	Output is correct
42	Correct	0 ms	212 KB	Output is correct
43	Correct	1 ms	300 KB	Output is correct
44	Correct	4 ms	852 KB	Output is correct
45	Correct	98 ms	14072 KB	Output is correct
46	Correct	1 ms	212 KB	Output is correct
47	Correct	1 ms	212 KB	Output is correct
48	Correct	0 ms	308 KB	Output is correct
49	Incorrect	16 ms	3788 KB	Answer gives possible 0 while actual possible 1
50	Halted	0 ms	0 KB	-

Subtask #6
0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	6 ms	1168 KB	Output is correct
7	Correct	149 ms	22008 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	6 ms	1108 KB	Output is correct
13	Correct	157 ms	21964 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	3 ms	724 KB	Output is correct
17	Correct	69 ms	12048 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Correct	39 ms	5704 KB	Output is correct
21	Correct	159 ms	21936 KB	Output is correct
22	Correct	165 ms	22020 KB	Output is correct
23	Correct	163 ms	22020 KB	Output is correct
24	Correct	158 ms	22048 KB	Output is correct
25	Correct	65 ms	12048 KB	Output is correct
26	Correct	90 ms	12036 KB	Output is correct
27	Correct	163 ms	21928 KB	Output is correct
28	Correct	151 ms	22036 KB	Output is correct
29	Correct	0 ms	212 KB	Output is correct
30	Correct	1 ms	212 KB	Output is correct
31	Correct	0 ms	212 KB	Output is correct
32	Correct	0 ms	212 KB	Output is correct
33	Correct	0 ms	212 KB	Output is correct
34	Correct	1 ms	212 KB	Output is correct
35	Correct	0 ms	212 KB	Output is correct
36	Correct	6 ms	1164 KB	Output is correct
37	Correct	149 ms	22020 KB	Output is correct
38	Correct	0 ms	212 KB	Output is correct
39	Correct	0 ms	212 KB	Output is correct
40	Correct	9 ms	1172 KB	Output is correct
41	Correct	233 ms	22036 KB	Output is correct
42	Correct	0 ms	212 KB	Output is correct
43	Correct	1 ms	300 KB	Output is correct
44	Correct	4 ms	852 KB	Output is correct
45	Correct	98 ms	14072 KB	Output is correct
46	Correct	1 ms	212 KB	Output is correct
47	Correct	1 ms	212 KB	Output is correct
48	Correct	0 ms	308 KB	Output is correct
49	Incorrect	16 ms	3788 KB	Answer gives possible 0 while actual possible 1
50	Halted	0 ms	0 KB	-

Submission #788232

Compilation message

Subtask #1 11.0 / 11.0

Subtask #2 10.0 / 10.0

Subtask #3 0 / 19.0

Subtask #4 0 / 35.0

Subtask #5 0 / 21.0

Subtask #6 0 / 4.0

Subtask #1
11.0 / 11.0

Subtask #2
10.0 / 10.0

Subtask #3
0 / 19.0

Subtask #4
0 / 35.0

Subtask #5
0 / 21.0

Subtask #6
0 / 4.0