Submission #1043703

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1043703	2024-08-04T14:21:04 Z	DeathIsAwe	Connecting Supertrees (IOI20_supertrees)	C++14	11 / 100	108 ms	22284 KB

supertrees

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

int construct(vector<vector<int>> p) {
	int n = p.size(), prev;
	vector<vector<int>> ans(n);
	bool visited[n];
	for (int i=0;i<n;i++) {
		visited[i] = false;
		for (int j=0;j<n;j++) {
			ans[i].push_back(0);
		}
	}
	vector<vector<int>> currentnodes(3);
	for (int i=0;i<n;i++) {
		if (visited[i]) {
			continue;
		}
		visited[i] = true;
		for (int j=0;j<3;j++) {
			currentnodes[j].clear();
		}
		for (int j=0;j<n;j++) {
			if (j == i) {
				continue;
			}
			if (p[i][j] > 0) {
				if (visited[j]) {
					return 0;
				}
				visited[j] = true;
				if (p[i][j] == 1) {
					currentnodes[1].push_back(j);
				} else if (p[i][j] == 2) {
					currentnodes[2].push_back(j);
				} else if (p[i][j] == 3) {
					return 0;
				}
			}
		}
		//for (int j: currentnodes[1]) {
		//	cout << j << ' ';
		//}
		//cout << '\n';
		//for (int j: currentnodes[2]) {
		//	cout << j << ' ';
		//}
		//cout << '\n';
		for (int j: currentnodes[1]) {
			for (int k=0;k<n;k++) {
				if (!visited[k]) {
					if (p[j][k] != 0) {
						return 0;
					}
				}
			}
		}
		for (int j: currentnodes[2]) {
			for (int k=0;k<n;k++) {
				if (!visited[k]) {
					if (p[j][k] != 0) {
						return 0;
					}
				}
			}
		}
		


		/*
		if (currentnodes[2].size() == 1) {
			return 0;
		}
		for (int j: currentnodes[1]) {
			for (int k: currentnodes[1]) {
				if (p[j][k] != 1) {
					return 0;
				}
			}
			for (int k: currentnodes[2]) {
				if (p[j][k] != 2) {
					return 0;
				}
			}
		}
		for (int j: currentnodes[2]) {
			for (int k: currentnodes[2]) {
				if (j == k) {
					continue;
				}
				if (p[j][k] != 2) {
					return 0;
				}
			}
		}
		*/
		prev = i;
		for (int j: currentnodes[1]) {
			ans[prev][j] = 1;
			ans[j][prev] = 1;
			prev = j;
		}
		prev = i;
		for (int j: currentnodes[2]) {
			ans[prev][j] = 1;
			ans[j][prev] = 1;
			prev = j;
		}
		if (prev == i) {
			continue;
		}
		ans[prev][i] = 1;
		ans[i][prev] = 1;
	}


	
	build(ans);
	return 1;
}

Subtask #1

11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	4 ms	1368 KB	Output is correct
7	Correct	94 ms	22144 KB	Output is correct

Subtask #2

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	4 ms	1368 KB	Output is correct
7	Correct	94 ms	22144 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	4 ms	1116 KB	Output is correct
13	Correct	99 ms	22280 KB	Output is correct
14	Correct	1 ms	344 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	2 ms	860 KB	Output is correct
17	Correct	53 ms	12312 KB	Output is correct
18	Correct	0 ms	344 KB	Output is correct
19	Incorrect	0 ms	348 KB	Answer gives possible 1 while actual possible 0
20	Halted	0 ms	0 KB	-

Subtask #3

0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	344 KB	Output is correct
4	Incorrect	0 ms	348 KB	Answer gives possible 1 while actual possible 0
5	Halted	0 ms	0 KB	-

Subtask #4

0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	29 ms	5824 KB	Output is correct
5	Correct	95 ms	22100 KB	Output is correct
6	Correct	101 ms	22100 KB	Output is correct
7	Correct	106 ms	22100 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	24 ms	5720 KB	Output is correct
10	Correct	108 ms	22284 KB	Output is correct
11	Correct	101 ms	22096 KB	Output is correct
12	Correct	103 ms	22100 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Incorrect	26 ms	5780 KB	Too many ways to get from 23 to 253, should be 1 found no less than 2
17	Halted	0 ms	0 KB	-

Subtask #5

0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	4 ms	1368 KB	Output is correct
7	Correct	94 ms	22144 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	4 ms	1116 KB	Output is correct
13	Correct	99 ms	22280 KB	Output is correct
14	Correct	1 ms	344 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	2 ms	860 KB	Output is correct
17	Correct	53 ms	12312 KB	Output is correct
18	Correct	0 ms	344 KB	Output is correct
19	Incorrect	0 ms	348 KB	Answer gives possible 1 while actual possible 0
20	Halted	0 ms	0 KB	-

Subtask #6

0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	4 ms	1368 KB	Output is correct
7	Correct	94 ms	22144 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	4 ms	1116 KB	Output is correct
13	Correct	99 ms	22280 KB	Output is correct
14	Correct	1 ms	344 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	2 ms	860 KB	Output is correct
17	Correct	53 ms	12312 KB	Output is correct
18	Correct	0 ms	344 KB	Output is correct
19	Incorrect	0 ms	348 KB	Answer gives possible 1 while actual possible 0
20	Halted	0 ms	0 KB	-