Submission #301121

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
301121	2020-09-17T16:38:47 Z	ElyesChaabouni	Connecting Supertrees (IOI20_supertrees)	C++14	21 / 100	280 ms	22392 KB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>

using namespace std;

int anc[200000], anc1[200000];
void get_anc(int x)
{
	int cu=anc[x];
	while(cu!=anc[cu])
		cu=anc[cu];
	anc[x]=cu;
}
void unite(int x, int y)
{
	get_anc(x);
	get_anc(y);
	if(anc[x]==anc[y])
		return;
	anc[anc[y]]=anc[x];
	anc[y]=anc[x];
}
void get_anc1(int x)
{
	int cu=anc1[x];
	while(cu!=anc1[cu])
		cu=anc1[cu];
	anc1[x]=cu;
}
void unite1(int x, int y)
{
	get_anc1(x);
	get_anc1(y);
	anc1[anc1[y]]=anc1[x];
	anc1[y]=anc1[x];
}
/*void build(vector<vector<int> >x)
{
	for(int i = 0; i < 2; i++)
	{
		for(int j = 0; j < 2; j++)
			cout << x[j][i] << ' ';
		cout << '\n';
	}
}*/
int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	std::vector<std::vector<int>> ans;
	for (int i = 0; i < n; i++) {
		std::vector<int> row;
		row.resize(n);
		ans.push_back(row);
	}
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			ans[i][j]=0;
	for(int i = 0; i < n; i++)
		anc[i]=i;
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			if(p[i][j]==1)
				unite(i, j);
		}
	}
	for(int i = 0; i < n; i++)
	{
		get_anc(i);
		//cout << anc[i] << ' ';
	}
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			if(((anc[i]==anc[j]) && (p[i][j]!=1)) || ((anc[i]!=anc[j]) && (p[i][j]==1)))
				return 0;
			if(p[i][j]==3)
				return 0;
		}
	}
	for(int i = 0; i < n; i++)
	{
		vector<int>v;
		for(int j = 0; j < n; j++)
		{
			if(anc[j]==i)
				v.push_back(j);
		}
		for(int j = 0; j < ((int)(v.size()))-1; j++)
		{
			ans[v[j]][v[j+1]]=1;
			ans[v[j+1]][v[j]]=1;
		}
	}
	for(int i = 0; i < n; i++)
		anc1[i]=-1;
	/*for(int i = 0; i < n; i++)
	{
		bool found=0;
		for(int j = 0; j < n && !found; j++)
		{
			if(anc[j]==i)
				found=1;
		}
		if(found)
			anc1[i]=i;
	}
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			if(p[i][j]==2)
			{
				get_anc(i);
				get_anc(j);
				unite1(anc[i], anc[j]);
			}
		}
	}
	for(int i = 0; i < n; i++)
	{
		vector<int>v;
		for(int j = 0; j < n; j++)
		{
			if(anc1[j]==i)
				v.push_back(j);
		}
		for(int j = 0; j < ((int)(v.size()))-1; j++)
		{
			ans[v[j]][v[j+1]]=1;
			ans[v[j+1]][v[j]]=1;
		}
		if(v.size() == 2)
			return 0;
		if(v.size() > 2)
		{
			ans[v[0]][v.back()]=1;
			ans[v.back()][v[0]]=1;
		}
	}*/
	for(int i = 0; i < n; i++)
		ans[i][i]=0;
	build(ans);
	return 1;
}
/*int main()
{
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	vector<vector<int> >a;
	int n;
	cin >> n;
	for(int i = 0; i < 2; i++)
	{
		vector<int>x;
		x.resize(2);
		a.push_back(x);
	}
	for(int i = 0; i < 2; i++)
		for(int j = 0; j < 2; j++)
			cin >> a[i][j];
	cout << construct(a) << '\n';
}*/

Subtask #1
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	0 ms	256 KB	Output is correct
3	Correct	0 ms	256 KB	Output is correct
4	Correct	0 ms	256 KB	Output is correct
5	Correct	0 ms	256 KB	Output is correct
6	Correct	11 ms	1280 KB	Output is correct
7	Correct	265 ms	22136 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	0 ms	256 KB	Output is correct
3	Correct	0 ms	256 KB	Output is correct
4	Correct	0 ms	256 KB	Output is correct
5	Correct	0 ms	256 KB	Output is correct
6	Correct	11 ms	1280 KB	Output is correct
7	Correct	265 ms	22136 KB	Output is correct
8	Correct	0 ms	256 KB	Output is correct
9	Correct	1 ms	256 KB	Output is correct
10	Correct	0 ms	256 KB	Output is correct
11	Correct	1 ms	256 KB	Output is correct
12	Correct	11 ms	1280 KB	Output is correct
13	Correct	254 ms	22104 KB	Output is correct
14	Correct	1 ms	256 KB	Output is correct
15	Correct	0 ms	256 KB	Output is correct
16	Correct	6 ms	768 KB	Output is correct
17	Correct	122 ms	12120 KB	Output is correct
18	Correct	0 ms	256 KB	Output is correct
19	Correct	0 ms	256 KB	Output is correct
20	Correct	67 ms	5752 KB	Output is correct
21	Correct	256 ms	22108 KB	Output is correct
22	Correct	253 ms	22392 KB	Output is correct
23	Correct	280 ms	22136 KB	Output is correct
24	Correct	251 ms	22136 KB	Output is correct
25	Correct	113 ms	12124 KB	Output is correct
26	Correct	109 ms	12156 KB	Output is correct
27	Correct	268 ms	22136 KB	Output is correct
28	Correct	255 ms	22136 KB	Output is correct

Subtask #3
0 / 19.0

#	Verdict	Memory	Grader output
1	Correct	256 KB	Output is correct
2	Correct	256 KB	Output is correct
3	Correct	256 KB	Output is correct
4	Incorrect	256 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	1 ms	256 KB	Output is correct
2	Incorrect	1 ms	256 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	0 ms	384 KB	Output is correct
2	Correct	0 ms	256 KB	Output is correct
3	Correct	0 ms	256 KB	Output is correct
4	Correct	0 ms	256 KB	Output is correct
5	Correct	0 ms	256 KB	Output is correct
6	Correct	11 ms	1280 KB	Output is correct
7	Correct	265 ms	22136 KB	Output is correct
8	Correct	0 ms	256 KB	Output is correct
9	Correct	1 ms	256 KB	Output is correct
10	Correct	0 ms	256 KB	Output is correct
11	Correct	1 ms	256 KB	Output is correct
12	Correct	11 ms	1280 KB	Output is correct
13	Correct	254 ms	22104 KB	Output is correct
14	Correct	1 ms	256 KB	Output is correct
15	Correct	0 ms	256 KB	Output is correct
16	Correct	6 ms	768 KB	Output is correct
17	Correct	122 ms	12120 KB	Output is correct
18	Correct	0 ms	256 KB	Output is correct
19	Correct	0 ms	256 KB	Output is correct
20	Correct	67 ms	5752 KB	Output is correct
21	Correct	256 ms	22108 KB	Output is correct
22	Correct	253 ms	22392 KB	Output is correct
23	Correct	280 ms	22136 KB	Output is correct
24	Correct	251 ms	22136 KB	Output is correct
25	Correct	113 ms	12124 KB	Output is correct
26	Correct	109 ms	12156 KB	Output is correct
27	Correct	268 ms	22136 KB	Output is correct
28	Correct	255 ms	22136 KB	Output is correct
29	Correct	0 ms	256 KB	Output is correct
30	Correct	0 ms	256 KB	Output is correct
31	Correct	0 ms	256 KB	Output is correct
32	Incorrect	0 ms	256 KB	Answer gives possible 1 while actual possible 0
33	Halted	0 ms	0 KB	-

Subtask #6
0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	0 ms	256 KB	Output is correct
3	Correct	0 ms	256 KB	Output is correct
4	Correct	0 ms	256 KB	Output is correct
5	Correct	0 ms	256 KB	Output is correct
6	Correct	11 ms	1280 KB	Output is correct
7	Correct	265 ms	22136 KB	Output is correct
8	Correct	0 ms	256 KB	Output is correct
9	Correct	1 ms	256 KB	Output is correct
10	Correct	0 ms	256 KB	Output is correct
11	Correct	1 ms	256 KB	Output is correct
12	Correct	11 ms	1280 KB	Output is correct
13	Correct	254 ms	22104 KB	Output is correct
14	Correct	1 ms	256 KB	Output is correct
15	Correct	0 ms	256 KB	Output is correct
16	Correct	6 ms	768 KB	Output is correct
17	Correct	122 ms	12120 KB	Output is correct
18	Correct	0 ms	256 KB	Output is correct
19	Correct	0 ms	256 KB	Output is correct
20	Correct	67 ms	5752 KB	Output is correct
21	Correct	256 ms	22108 KB	Output is correct
22	Correct	253 ms	22392 KB	Output is correct
23	Correct	280 ms	22136 KB	Output is correct
24	Correct	251 ms	22136 KB	Output is correct
25	Correct	113 ms	12124 KB	Output is correct
26	Correct	109 ms	12156 KB	Output is correct
27	Correct	268 ms	22136 KB	Output is correct
28	Correct	255 ms	22136 KB	Output is correct
29	Correct	0 ms	256 KB	Output is correct
30	Correct	0 ms	256 KB	Output is correct
31	Correct	0 ms	256 KB	Output is correct
32	Incorrect	0 ms	256 KB	Answer gives possible 1 while actual possible 0
33	Halted	0 ms	0 KB	-

Submission #301121

Compilation message

Subtask #1 11.0 / 11.0

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

Subtask #3
0 / 19.0

Subtask #4
0 / 35.0

Subtask #5
0 / 21.0

Subtask #6
0 / 4.0