Submission #756178

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
756178	2023-06-11T09:13:42 Z	Trumling	Connecting Supertrees (IOI20_supertrees)	C++14	11 / 100	212 ms	25996 KB

supertrees

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

typedef long long ll;
#define pb push_back
#define F first
#define S second
#define enter cout<<'\n';
#define INF 99999999999999999
#define MOD 1000000007
#define all(x) x.begin(),x.end()

vector<bool>vis(1000,0);
vector<bool>vis2(1000,0);

vector<vector<int>>g;
vector<vector<int>>ans;
ll nn;
bool dfs1(int start,int beg)
{
	vis[start]=1;
	//for(int i=0;i<nn;i++)
		//if(g[start][i]!=g[beg][i] && i!=start && i!=beg)
			//return 0;

	for(int i=0;i<nn;i++)
		if(!vis[i] && g[start][i]==1)
		{
			ans[i][start]=1;
			ans[start][i]=1;
			return dfs1(i,beg);
		}
	
	return 1;
}

bool dfs2(int start,int beg)
{
	vis2[start]=1;
	//for(int i=0;i<nn;i++)
		//if(g[start][i]!=g[beg][i] && i!=start && i!=beg)
			//return 0;
		
		

	ll count=0;
	for(int i=0;i<nn;i++)
		if(g[start][i]==2)
		count++;
	
	if(count==1)
	return 0;

	for(int i=0;i<nn;i++)
		if(!vis2[i] && g[start][i]==2)
		{
			ans[i][start]=1;
			ans[start][i]=1;

			return dfs2(i,beg);
		}
	ans[start][beg]=1;
	ans[beg][start]=1;
	return 1;
}

int construct(vector<vector<int>> pr) 
{
	nn=pr.size();
	g=pr;

	ans.assign(nn,vector<int>(nn,0));

	for(int i=0;i<nn;i++)
	{
		bool now=dfs1(i,i);
		if(!now)
		return 0;
	}

	for(int i=0;i<nn;i++)
	{
		bool now=dfs2(i,i);
		if(!now)
		return 0;
	}

	for(int i=0;i<nn;i++)
	ans[i][i]=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	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	8 ms	1356 KB	Output is correct
7	Correct	167 ms	25988 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	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	8 ms	1356 KB	Output is correct
7	Correct	167 ms	25988 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	300 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	8 ms	1356 KB	Output is correct
13	Correct	166 ms	25932 KB	Output is correct
14	Incorrect	0 ms	212 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	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	1 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	8 ms	1236 KB	Output is correct
9	Correct	174 ms	25948 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	8 ms	1236 KB	Output is correct
13	Correct	178 ms	25960 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Incorrect	0 ms	212 KB	Answer gives possible 1 while actual possible 0
16	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	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	42 ms	6732 KB	Output is correct
5	Correct	178 ms	25996 KB	Output is correct
6	Correct	179 ms	25888 KB	Output is correct
7	Correct	212 ms	25912 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	47 ms	6808 KB	Output is correct
10	Correct	181 ms	25936 KB	Output is correct
11	Correct	187 ms	25984 KB	Output is correct
12	Correct	176 ms	25988 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Incorrect	0 ms	212 KB	Too many ways to get from 0 to 4, should be 1 found no less than 2
16	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	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	8 ms	1356 KB	Output is correct
7	Correct	167 ms	25988 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	300 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	8 ms	1356 KB	Output is correct
13	Correct	166 ms	25932 KB	Output is correct
14	Incorrect	0 ms	212 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	1 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	8 ms	1356 KB	Output is correct
7	Correct	167 ms	25988 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	300 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	8 ms	1356 KB	Output is correct
13	Correct	166 ms	25932 KB	Output is correct
14	Incorrect	0 ms	212 KB	Answer gives possible 1 while actual possible 0
15	Halted	0 ms	0 KB	-