Submission #125470

#	Time	Username	Problem	Language	Result	Execution time	Memory
125470		anayk	Izlet (COI19_izlet)	C++14	100 / 100	1053 ms	96568 KiB

izlet

#include <iostream>
#include <vector>
#include <set>
 
#define MAXN 3005
 
int n;
int par1[MAXN];
int par2[MAXN];
int sec[MAXN][MAXN];
int f[MAXN][MAXN];
std::vector<int> Adj[MAXN];
bool mark[MAXN];
 
int root(int u, int par[])
{
	if(par[u] < 0)
		return u;
	
	return par[u] = root(par[u], par);
}
 
void merge(int u, int v, int par[])
{
	u = root(u, par);
	v = root(v, par);
 
	if(u == v)
		return;
 
	if(par[u] > par[v])
		u ^= v ^= u ^= v;
 
	par[u] += par[v];
	par[v] = u;
}
 
void dfs(int u, int p, int x, int y)
{
	
	sec[x][u] = y;
 
	for(int v : Adj[u])
	{
		if(v != p)
			dfs(v, u, x, y);
	}
}

void check(int u, int p, int x, std::set<int> cur)
{
	cur.insert(root(u, par1));
	if(cur.size() != f[u][x])
		std::cout << u << " " << x << " " << cur.size() << " " << f[u][x] << std::endl;

	for(int v : Adj[u])
	{
		std::set<int> temp = cur;
		if(v != p)
			check(v, u, x, temp);
	}
}

int main()
{
	std::ios::sync_with_stdio(false);

	std::cin >> n >> n;

	for(int i = 0; i < n; i++)
	{
		par1[i] = par2[i] = -1;
		mark[i] = false;
	}

	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			std::cin >> f[i][j];

			if(f[i][j] == 1)
				merge(i, j, par1);
		}
	}

	for(int i = 0; i < n; i++)
	{
		if(par1[i] >= 0)
		{
			mark[i] = true;
			int j = root(i, par1);
			Adj[i].push_back(j);
			Adj[j].push_back(i);
			continue;
		}
 
		for(int j = i+1; j < n; j++)
		{
			if(par1[j] >= 0)
				continue;
 
			if(f[i][j] == 2)
			{
				if(root(i, par2) == root(j, par2))
					continue;

				Adj[i].push_back(j);
				Adj[j].push_back(i);
				merge(i, j, par2);
			}
		}
	}
 
	for(int i = 0; i < n; i++)
	{
		if(par1[i] >= 0)
			continue;
 
		for(int j : Adj[i])
			dfs(j, i, i, j);
	}

	for(int i = 0; i < n; i++)
	{
		if(mark[i])
			continue;

		for(int j = i+1; j < n; j++)
		{
			if(mark[j])
				continue;

			int x = sec[i][j];
			int y = sec[j][i];

			if((f[i][j] == f[x][j]) && (f[i][j] == f[i][y]) && (f[i][j] == (f[x][y] + 1)))
				merge(i, j, par1);
		}
	}
 	
 // 	std::set<int> cur;
	// for(int i = 0; i < n; i++)
	// 	check(i, -1, i, cur);

	// std::cout << " done " << std::endl;

	for(int i = 0; i < n; i++)
		std::cout << root(i, par1)+1 << " ";
 
	std::cout << std::endl;
 
	for(int i = 0; i < n; i++)
	{
		for(int j : Adj[i])
		{
			if(i < j)
				std::cout << i+1 << " " << j+1 << std::endl;
		}
	}
 
	// for(std::pair<int, int> x : extra)
	// {
	// 	std::cout << x.first+1 << " " << x.second+1 << std::endl;
	// }
}

Compilation message (stderr)

izlet.cpp: In function 'void check(int, int, int, std::set<int>)':
izlet.cpp:53:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(cur.size() != f[u][x])
     ~~~~~~~~~~~^~~~~~~~~~

• Subtask 1: 18 / 18
• Subtask 2: 25 / 25
• Subtask 3: 57 / 57