oj.uz

Submission #125449

# Submission time Handle Problem Language Result Execution time Memory
125449 2019-07-05T10:32:08 Z anayk Izlet (COI19_izlet) C++14
18 / 100
 830 ms 88924 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::ios::sync_with_stdio(false);

	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)
			{
				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(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
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 830 ms 88924 KB Output is correct
3 Correct 813 ms 88824 KB Output is correct
4 Correct 748 ms 69448 KB Output is correct
5 Correct 787 ms 81164 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 809 ms 83380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 830 ms 88924 KB Output is correct
3 Correct 813 ms 88824 KB Output is correct
4 Correct 748 ms 69448 KB Output is correct
5 Correct 787 ms 81164 KB Output is correct
6 Incorrect 809 ms 83380 KB Output isn't correct
7 Halted 0 ms 0 KB -