Submission #1078686

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1078686	2024-08-28T04:27:17 Z	Muhammad_Aneeq	Connecting Supertrees (IOI20_supertrees)	C++17	11 / 100	119 ms	24060 KB

supertrees

#include <vector>
using namespace std;
void build(vector<vector<int>> b);
int construct(vector<vector<int>> p)
{
	int n=p.size();
	bool subt1=1,subt2=1;
	for (int i=0;i<n;i++)
	{
		for (int j=i+1;j<n;j++)
		{
			if (p[i][j]!=1)
				subt1=0;
			if (p[i][j]>1)
				subt2=0;
		}
	}
	if (subt1)
	{
		vector<vector<int>>b(n,vector<int>(n));
		for (int i=1;i<n;i++)
			b[0][i]=b[i][0]=1;
		build(b);
		return 1;
	}
	if (subt2)
	{
		bool vis[n]={};
		int head[n]={};
		vector<vector<int>>b(n,vector<int>(n));
		for (int i=0;i<n;i++)
		{
			if (!vis[i])
			{
				vis[i]=1;
				for (int j=0;j<n;j++)
				{
					if (vis[j])
						continue;
					if (p[i][j])
					{
						vis[j]=1;
						b[i][j]=1;
						head[j]=i;
					}
				}
			}
		}
		for (int i=0;i<n;i++)
		{
			for (int j=0;j<n;j++)
			{
				if (p[i][j]&&head[i]!=head[j])
					return 0;
			}
		}
		build(b);
		return 1;
	}
	return 0;
}

Subtask #1

11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	344 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	6 ms	1372 KB	Output is correct
7	Correct	112 ms	23888 KB	Output is correct

Subtask #2

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	344 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	6 ms	1372 KB	Output is correct
7	Correct	112 ms	23888 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	1 ms	344 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	6 ms	1372 KB	Output is correct
13	Correct	119 ms	24060 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	3 ms	860 KB	Output is correct
17	Correct	89 ms	14064 KB	Output is correct
18	Incorrect	0 ms	348 KB	Answer gives possible 1 while actual possible 0
19	Halted	0 ms	0 KB	-

Subtask #3

0 / 19.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	Incorrect	0 ms	348 KB	Answer gives possible 0 while actual possible 1
6	Halted	0 ms	0 KB	-

Subtask #4

0 / 35.0

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

Subtask #5

0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	344 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	6 ms	1372 KB	Output is correct
7	Correct	112 ms	23888 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	1 ms	344 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	6 ms	1372 KB	Output is correct
13	Correct	119 ms	24060 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	3 ms	860 KB	Output is correct
17	Correct	89 ms	14064 KB	Output is correct
18	Incorrect	0 ms	348 KB	Answer gives possible 1 while actual possible 0
19	Halted	0 ms	0 KB	-

Subtask #6

0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	344 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	6 ms	1372 KB	Output is correct
7	Correct	112 ms	23888 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	1 ms	344 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	6 ms	1372 KB	Output is correct
13	Correct	119 ms	24060 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	3 ms	860 KB	Output is correct
17	Correct	89 ms	14064 KB	Output is correct
18	Incorrect	0 ms	348 KB	Answer gives possible 1 while actual possible 0
19	Halted	0 ms	0 KB	-