Submission #779729

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
779729	2023-07-11T17:40:44 Z	Malix	Connecting Supertrees (IOI20_supertrees)	C++14	11 / 100	155 ms	23960 KB

supertrees

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

using namespace std;

int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	std::vector<std::vector<int>> answer;
	for (int i = 0; i < n; i++) {
		std::vector<int> row;
		row.resize(n);
		answer.push_back(row);
	}

	if(n==1){
		answer[0][0] = 0;
		build(answer);
		return 1;
	}

	int count = 0;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			if(p[i][j] == 1){
				count++;
			}
		}
	}

	//change this later
	if(count == n){
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				answer[i][j] = 0;
			}
		}
		build(answer);
		return 1;
	}


	else if(count == n*n){
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				answer[i][j] = 0;
			}
		}
		for(int i = 1; i < n; i++){
			answer[i][0] = 1;
			answer[0][i] = 1;
		}
		build(answer);
		return 1;
	}

	count = 0;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			if(p[i][j] <= 1){
				count++;
			}
		}
	}
	if(count == n*n){

		vector<int> arr(n, 0);
		vector<int> arr2;
		int arr2size;

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

		int currentIndex = 0;

		while(currentIndex != n){

			if(!arr[currentIndex]){
				arr2.push_back(currentIndex);
				for(int i = 0; i < n; i++){
					if(p[currentIndex][i]){
						if(arr[i]){
							return 0;
						}
						answer[currentIndex][i] = 1;
						answer[i][currentIndex] = 1;
						if(currentIndex != i){
							arr[i]++;
						}
						arr2.push_back(i);
						

					}
				}
				arr2size = arr2.size();
				for(int k = 0; k < arr2size-1; k++){
					for(int m = k+1; m < arr2size; m++){
						if(!p[arr2[k]][arr2[m]]){
							return 0;
						}
					}
				}

				arr[currentIndex]++;
				arr2.clear();
			}

			
			currentIndex++;
		}
	
		
		for(int i = 0 ; i < n; i++){
			if(arr[i] > 1){
				return 0;
			}
		}
		
		

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

		build(answer);
		return 1;
	}


	build(answer);
	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	1 ms	284 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	292 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	6 ms	1200 KB	Output is correct
7	Correct	144 ms	22532 KB	Output is correct

Subtask #2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	284 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	292 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	6 ms	1200 KB	Output is correct
7	Correct	144 ms	22532 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	6 ms	1236 KB	Output is correct
13	Correct	142 ms	22548 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	852 KB	Output is correct
17	Correct	70 ms	14072 KB	Output is correct
18	Correct	1 ms	288 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Correct	36 ms	6252 KB	Output is correct
21	Correct	144 ms	23960 KB	Output is correct
22	Correct	138 ms	23884 KB	Output is correct
23	Correct	148 ms	23908 KB	Output is correct
24	Correct	148 ms	23928 KB	Output is correct
25	Incorrect	155 ms	23908 KB	Answer gives possible 1 while actual possible 0
26	Halted	0 ms	0 KB	-

Subtask #3
0 / 19.0

#	Verdict	Memory	Grader output
1	Correct	212 KB	Output is correct
2	Correct	212 KB	Output is correct
3	Correct	212 KB	Output is correct
4	Incorrect	288 KB	Answer gives possible 1 while actual possible 0
5	Halted	0 KB	-

Subtask #4
0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Incorrect	1 ms	284 KB	Too few ways to get from 0 to 1, should be 2 found 0
3	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	1 ms	284 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	292 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	6 ms	1200 KB	Output is correct
7	Correct	144 ms	22532 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	6 ms	1236 KB	Output is correct
13	Correct	142 ms	22548 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	852 KB	Output is correct
17	Correct	70 ms	14072 KB	Output is correct
18	Correct	1 ms	288 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Correct	36 ms	6252 KB	Output is correct
21	Correct	144 ms	23960 KB	Output is correct
22	Correct	138 ms	23884 KB	Output is correct
23	Correct	148 ms	23908 KB	Output is correct
24	Correct	148 ms	23928 KB	Output is correct
25	Incorrect	155 ms	23908 KB	Answer gives possible 1 while actual possible 0
26	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	1 ms	284 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	292 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	6 ms	1200 KB	Output is correct
7	Correct	144 ms	22532 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	6 ms	1236 KB	Output is correct
13	Correct	142 ms	22548 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	852 KB	Output is correct
17	Correct	70 ms	14072 KB	Output is correct
18	Correct	1 ms	288 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Correct	36 ms	6252 KB	Output is correct
21	Correct	144 ms	23960 KB	Output is correct
22	Correct	138 ms	23884 KB	Output is correct
23	Correct	148 ms	23908 KB	Output is correct
24	Correct	148 ms	23928 KB	Output is correct
25	Incorrect	155 ms	23908 KB	Answer gives possible 1 while actual possible 0
26	Halted	0 ms	0 KB	-

Submission #779729

Compilation message

Subtask #1 11.0 / 11.0

Subtask #2 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
0 / 10.0

Subtask #3
0 / 19.0

Subtask #4
0 / 35.0

Subtask #5
0 / 21.0

Subtask #6
0 / 4.0