Submission #1078814

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1078814	2024-08-28T06:32:20 Z	Faisal_Saqib	Connecting Supertrees (IOI20_supertrees)	C++17	11 / 100	142 ms	31316 KB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
const int N=1e3;
int reach[N][N],tree_case[N][N];
int par[N],par1[N];
void init(int n)
{
	for(int i=0;i<n;i++)
		par[i]=par1[i]=i;
}
int get(int x)
{
	if(par[x]==x)return x;
	return par[x]=get(par[x]);
}
int get1(int x)
{
	if(par1[x]==x)return x;
	return par1[x]=get1(par1[x]);
}
bool merge(int x,int y)
{
	x=get(x);
	y=get(y);
	if(x==y)return 0;
	par[y]=x;
	return 1;
}
bool merge1(int x,int y)
{
	x=get1(x);
	y=get1(y);
	if(x==y)return 0;
	par1[y]=x;
	return 1;
}
vector<int> ma[N];
int head;
void dfs(int x)
{
	reach[head][x]=1;
	for(auto y:ma[x])
		if(!reach[head][y])
			dfs(y);
}
int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	init(n);
	for(int i=0;i<n;i++)
	{
		if(p[i][i]!=1) // i i is always one
			return 0;
		for(int j=0;j<n;j++)
			tree_case[i][j]=reach[i][j]=0;
	}
	for(int i=0;i<n;i++)
	{
		for(int j=i+1;j<n;j++)
		{
			if(p[i][j]==1)
			{
				tree_case[i][j]=tree_case[j][i]=merge1(i,j);
			}
		}
	}
	for(int i=0;i<n;i++)
	{
		if(i==get(i))
		{
			vector<int> cur={i};
			for(int j=i+1;j<n;j++)
			{
				if(get(j)==j)
				{
					bool han=1;
					for(auto k:cur)
					{
						if(p[k][j]!=2)
						{
							han=0;
							break;
						}
					}
					if(han)
					{
						cur.push_back(j);
						merge(i,j);
					}
				}
			}
			if(cur.size()==1)continue;
			if(cur.size()==2)
				return 0;
			cur.push_back(i);
			for(int j=1;j<cur.size();j++)
			{
				int x=cur[j-1];
				int y=cur[j];
				tree_case[x][y]=tree_case[y][x]=1;
				merge(x,y);
			}
		}
	}
	for(int i=0;i<n;i++)
	{
		for(int j=i+1;j<n;j++)
		{	
			if(tree_case[i][j])
			{
				ma[i].push_back(j);
				ma[j].push_back(i);
			}
		}
	}
	vector<vector<int>> answer(n,vector<int>(n,0));
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			answer[i][j]=tree_case[i][j];
			reach[i][j]=0;
		}
		// head=i;
		// dfs(i);
		// for(int j=0;j<n;j++)
		// {
		// 	p[i][j]-=(p[i][j]==2);// make 2 to 1
		// 	if(reach[i][j]!=p[i][j])
		// 	{
		// 		return 0;
		// 	}
		// }
	}
	build(answer);
	return 1;
}

Compilation message

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:96:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |    for(int j=1;j<cur.size();j++)
      |                ~^~~~~~~~~~~

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	2928 KB	Output is correct
7	Correct	126 ms	30036 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	2928 KB	Output is correct
7	Correct	126 ms	30036 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	468 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	344 KB	Output is correct
12	Correct	5 ms	2908 KB	Output is correct
13	Correct	142 ms	31304 KB	Output is correct
14	Incorrect	0 ms	348 KB	Answer gives possible 1 while actual possible 0
15	Halted	0 ms	0 KB	-

Subtask #3
0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	472 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	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	6 ms	2904 KB	Output is correct
9	Correct	122 ms	31188 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	2908 KB	Output is correct
13	Correct	136 ms	31144 KB	Output is correct
14	Incorrect	0 ms	344 KB	Answer gives possible 1 while actual possible 0
15	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	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	33 ms	10124 KB	Output is correct
5	Correct	127 ms	31268 KB	Output is correct
6	Correct	118 ms	31312 KB	Output is correct
7	Correct	138 ms	31296 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	31 ms	10144 KB	Output is correct
10	Correct	119 ms	31264 KB	Output is correct
11	Correct	133 ms	31316 KB	Output is correct
12	Correct	134 ms	31312 KB	Output is correct
13	Correct	0 ms	344 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Incorrect	15 ms	6688 KB	Answer gives possible 0 while actual possible 1
17	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	2928 KB	Output is correct
7	Correct	126 ms	30036 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	468 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	344 KB	Output is correct
12	Correct	5 ms	2908 KB	Output is correct
13	Correct	142 ms	31304 KB	Output is correct
14	Incorrect	0 ms	348 KB	Answer gives possible 1 while actual possible 0
15	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	2928 KB	Output is correct
7	Correct	126 ms	30036 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	468 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	344 KB	Output is correct
12	Correct	5 ms	2908 KB	Output is correct
13	Correct	142 ms	31304 KB	Output is correct
14	Incorrect	0 ms	348 KB	Answer gives possible 1 while actual possible 0
15	Halted	0 ms	0 KB	-

Submission #1078814

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