oj.uz

Submission #975303

# Submission time Handle Problem Language Result Execution time Memory
975303 2024-05-04T17:54:23 Z raspy Connecting Supertrees (IOI20_supertrees) C++14
11 / 100
 155 ms 24660 KB 
#include "supertrees.h"
#include <vector>
#include <iostream>

using namespace std;

bool obd[20005];
int dis[20005];
vector<int> el[20005];

int par(int x)
{
	return dis[x] = (dis[x] == x ? x : par(dis[x]));
}

void zd(int x, int y, bool zlij = true)
{
	x = par(x);
	y = par(y);
	if (x == y)
		return;
	if (el[x].size() < el[y].size())
		swap(x, y);
	if (zlij)
	{
		for (auto e : el[y])
			el[x].push_back(e);
	}
	el[y].clear();
	dis[y] = x;
	return;
}

int construct(vector<vector<int>> p)
{
	int n = p.size();
	vector<vector<int>> gr(n, vector<int>(n, 0));
	for (int i = 0; i < n; i++)
	{
		el[i].push_back(i);
		dis[i] = i;
	}
	for (int i = 0; i < n; i++)
		for (int j = i+1; j < n; j++)
		{
			if (p[i][j] == 1 && par(i)-par(j))
			{
				gr[par(i)][par(j)] = gr[par(j)][par(i)] = 1;
				zd(i, j);
			}
		}
	for (int i = 0; i < n; i++)
	{
		int x = par(i);
		if (obd[x])
			continue;
		obd[x] = true;
		vector<int> dv;
		for (int j = 0; j < n; j++)
		{
			if (p[x][j] == 2)
			{
				if (par(x) == par(j) || el[j].empty())
					return 0;
				zd(x, j, false);
				dv.push_back(j);
			}
		}
		vector<int>& vsi = el[i];
		for (int k = 1; k < vsi.size(); k++)
		{
			int cnt = 0;
			for (int j = 0; j < n; j++)
			{
				if (p[vsi[k]][j] == 2)
				{
					if (par(vsi[k]) != par(j))
						return 0;
					zd(vsi[k], j, false);
					cnt++;
				}
			}
			if (cnt != dv.size())
				return 0;
		}
		if (!dv.empty())
		{
			if (dv.size() < 2)
				return 0;
			gr[x][dv[0]] = 1;
			gr[dv[0]][x] = 1;
			dv.push_back(x);
			for (int k = 0; k < dv.size()-1; k++)
				gr[dv[k]][dv[k+1]] = gr[dv[k+1]][dv[k]] = 1;
		}
	}
	build(gr);
	return 1;
}

Compilation message

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:70:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |   for (int k = 1; k < vsi.size(); k++)
      |                   ~~^~~~~~~~~~~~
supertrees.cpp:83:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |    if (cnt != dv.size())
      |        ~~~~^~~~~~~~~~~~
supertrees.cpp:93:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |    for (int k = 0; k < dv.size()-1; k++)
      |                    ~~^~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1016 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 908 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 7 ms 1892 KB Output is correct
7 Correct 151 ms 24444 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1016 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 908 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 7 ms 1892 KB Output is correct
7 Correct 151 ms 24444 KB Output is correct
8 Correct 1 ms 856 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 1 ms 908 KB Output is correct
12 Correct 7 ms 1884 KB Output is correct
13 Correct 147 ms 24532 KB Output is correct
14 Incorrect 1 ms 856 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 1 ms 856 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 856 KB Output is correct
8 Correct 7 ms 1884 KB Output is correct
9 Correct 149 ms 24600 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 6 ms 1884 KB Output is correct
13 Correct 146 ms 24460 KB Output is correct
14 Correct 1 ms 860 KB Output is correct
15 Correct 1 ms 860 KB Output is correct
16 Correct 3 ms 1372 KB Output is correct
17 Correct 64 ms 14680 KB Output is correct
18 Incorrect 1 ms 860 KB Answer gives possible 1 while actual possible 0
19 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 1 ms 856 KB Output is correct
3 Correct 1 ms 872 KB Output is correct
4 Correct 37 ms 6820 KB Output is correct
5 Correct 155 ms 24660 KB Output is correct
6 Correct 148 ms 24508 KB Output is correct
7 Correct 152 ms 24420 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 37 ms 6692 KB Output is correct
10 Correct 149 ms 24568 KB Output is correct
11 Correct 149 ms 24596 KB Output is correct
12 Correct 153 ms 24420 KB Output is correct
13 Correct 1 ms 856 KB Output is correct
14 Correct 1 ms 856 KB Output is correct
15 Correct 1 ms 860 KB Output is correct
16 Incorrect 15 ms 4188 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 1 ms 1016 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 908 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 7 ms 1892 KB Output is correct
7 Correct 151 ms 24444 KB Output is correct
8 Correct 1 ms 856 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 1 ms 908 KB Output is correct
12 Correct 7 ms 1884 KB Output is correct
13 Correct 147 ms 24532 KB Output is correct
14 Incorrect 1 ms 856 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 1016 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 908 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 7 ms 1892 KB Output is correct
7 Correct 151 ms 24444 KB Output is correct
8 Correct 1 ms 856 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 1 ms 908 KB Output is correct
12 Correct 7 ms 1884 KB Output is correct
13 Correct 147 ms 24532 KB Output is correct
14 Incorrect 1 ms 856 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -