oj.uz

Submission #125467

# Submission time Handle Problem Language Result Execution time Memory
125467 2019-07-05T11:48:11 Z anayk Izlet (COI19_izlet) C++14
18 / 100
 1058 ms 109816 KB 
#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];
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);
	}
}

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;

	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)
		{
			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++)
	{
		for(int j = i+1; j < n; j++)
		{
			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;
	// }
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 907 ms 71356 KB Output is correct
3 Correct 916 ms 71260 KB Output is correct
4 Correct 791 ms 51800 KB Output is correct
5 Correct 848 ms 63644 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 855 ms 65820 KB Output is correct
2 Correct 880 ms 74488 KB Output is correct
3 Correct 1058 ms 109048 KB Output is correct
4 Correct 1058 ms 109816 KB Output is correct
5 Incorrect 744 ms 65400 KB Output isn't correct
6 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 907 ms 71356 KB Output is correct
3 Correct 916 ms 71260 KB Output is correct
4 Correct 791 ms 51800 KB Output is correct
5 Correct 848 ms 63644 KB Output is correct
6 Correct 855 ms 65820 KB Output is correct
7 Correct 880 ms 74488 KB Output is correct
8 Correct 1058 ms 109048 KB Output is correct
9 Correct 1058 ms 109816 KB Output is correct
10 Incorrect 744 ms 65400 KB Output isn't correct
11 Halted 0 ms 0 KB -