oj.uz

Submission #975304

# Submission time Handle Problem Language Result Execution time Memory
975304 2024-05-04T17:57:55 Z raspy Connecting Supertrees (IOI20_supertrees) C++14
11 / 100
 171 ms 22660 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))
				// 	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 860 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 856 KB Output is correct
5 Correct 0 ms 860 KB Output is correct
6 Correct 7 ms 1628 KB Output is correct
7 Correct 149 ms 22516 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 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 856 KB Output is correct
5 Correct 0 ms 860 KB Output is correct
6 Correct 7 ms 1628 KB Output is correct
7 Correct 149 ms 22516 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 860 KB Output is correct
12 Correct 7 ms 1628 KB Output is correct
13 Correct 146 ms 22512 KB Output is correct
14 Incorrect 1 ms 860 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 860 KB Output is correct
2 Correct 1 ms 856 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Incorrect 1 ms 860 KB Answer gives possible 1 while actual possible 0
5 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 38 ms 6228 KB Output is correct
5 Correct 146 ms 22496 KB Output is correct
6 Correct 171 ms 22500 KB Output is correct
7 Correct 151 ms 22660 KB Output is correct
8 Correct 1 ms 856 KB Output is correct
9 Correct 40 ms 6392 KB Output is correct
10 Correct 148 ms 22500 KB Output is correct
11 Correct 145 ms 22496 KB Output is correct
12 Correct 149 ms 22504 KB Output is correct
13 Correct 0 ms 856 KB Output is correct
14 Correct 1 ms 860 KB Output is correct
15 Correct 1 ms 860 KB Output is correct
16 Incorrect 37 ms 6236 KB Too many ways to get from 0 to 250, should be 2 found no less than 3
17 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 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 856 KB Output is correct
5 Correct 0 ms 860 KB Output is correct
6 Correct 7 ms 1628 KB Output is correct
7 Correct 149 ms 22516 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 860 KB Output is correct
12 Correct 7 ms 1628 KB Output is correct
13 Correct 146 ms 22512 KB Output is correct
14 Incorrect 1 ms 860 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 860 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 856 KB Output is correct
5 Correct 0 ms 860 KB Output is correct
6 Correct 7 ms 1628 KB Output is correct
7 Correct 149 ms 22516 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 860 KB Output is correct
12 Correct 7 ms 1628 KB Output is correct
13 Correct 146 ms 22512 KB Output is correct
14 Incorrect 1 ms 860 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -