oj.uz

Submission #124227

# Submission time Handle Problem Language Result Execution time Memory
124227 2019-07-02T20:03:02 Z anayk Izlet (COI19_izlet) C++14
0 / 100
 2000 ms 35924 KB 
#include <iostream>
#include <vector>

#define MAXN 3005

int n;
int par1[MAXN];
int par2[MAXN];
int sec[MAXN][MAXN];
int f[MAXN][MAXN];
std::vector<int> Adj[MAXN];
std::vector<std::pair<int, int> > extra;

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);
	}
}

int main()
{
	std::cin >> n >> n;

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

	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)
		{
			extra.push_back({i, root(i, par1)});
			continue;
		}

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

			if((f[i][j] == 2) && (root(i, par2) != root(j, par2)))
			{
				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(par1[i] >= 0)
			continue;

		for(int j = i+1; j < n; j++)
		{
			if(par1[j] >= 0)
				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);
		}
	}

	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;
	}
}

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 632 KB Output is correct
2 Execution timed out 2033 ms 35100 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2041 ms 35924 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 632 KB Output is correct
2 Execution timed out 2033 ms 35100 KB Time limit exceeded
3 Halted 0 ms 0 KB -