Submission #373451

#	Time	Username	Problem	Language	Result	Execution time	Memory
373451		pggp	Izlet (COI19_izlet)	C++14	18 / 100	578 ms	35932 KiB

izlet

#include <bits/stdc++.h>

using namespace std;

int matrix[3005][3005];

int n;

void task1();
void task2();

int main(){
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(false);

	int task;
	cin >> task;

	cin >> n;

	for (int x = 1; x <= n; ++x)
	{
		for (int y = 1; y <= n; ++y)
		{
			cin >> matrix[x][y];
		}
	}

	if(task == 1){
		task1();
	}
	if(task == 2){
		task2();
	}
}

int first, last;

bool comp(int a, int b){
	if(matrix[a][first] > matrix[b][first]){
		return true;
	}
	if(matrix[a][last] < matrix[b][last]){
		return true;
	}
	return false;
}

int colors[4000];
void task2(){
	cout << 1 << " ";
	colors[1] = 1;


	int prev = 1;
	for (int x = 1; x <= n; ++x)
	{
		for(int i = x - 1; i > 0; i--){
			if(matrix[i][x] == matrix[i][prev]){
				colors[x] = colors[i];
				cout << colors[x] << " ";
				break;
			}
		}
		if(colors[x] == 0){
			colors[x] = x;
			cout << colors[x] << " ";
		}
	}
	cout << endl;


	for (int x = 1; x < n; ++x)
	{
		cout << x << " " << x + 1 << endl;
	}

}


int parent[3005];
void un(int x, int y){
	if(parent[x] == parent[y]){
		return;
	}
	int par_x = parent[x];
	for (int i = 1; i <= n; ++i)
	{
		if(parent[i] == par_x){
			parent[i] = parent[y];
		}
	}
}


void two_groups();
void one_group();

void task1(){
	for (int x = 1; x <= n; ++x)
	{
		parent[x] = x;
	}
	for (int x = 1; x <= n; ++x)
	{
		for (int y = 1; y <= n; ++y)
		{
			if(matrix[x][y] == 1 and x != y){
				un(x, y);
			}
		}
	}

	for (int i = 1; i <= n; ++i)
	{
		
		//cout << i << " has a parent " << parent[i] << endl;
	}

	//int two_groups;
	for (int x = 1; x <= n; ++x)
	{
		if(parent[x] != parent[1]){
			two_groups();
			return;
		}
	}
	one_group();
}

void one_group(){
	for (int i = 0; i < n; ++i)
	{
		cout << "1 ";
	}
	cout << endl;
	for (int i = 1; i < n; ++i)
	{
		cout << i << " " << i + 1 << endl;
	}
}

vector < int > gr[3005];

void two_groups(){
	
	gr[1].push_back(1);
	cout << 2 << " ";
	for (int x = 2; x <= n; ++x)
	{
		if(parent[x] == parent[1]){
			cout << 2 << " ";
		}
		else{
			cout << 1 << " ";
		}
		gr[parent[x]].push_back(x);
	}
	cout << endl;
	for (int j = 1; j < 3005; ++j)
	{
		for (int i = 0; i < ((int)gr[j].size() - 1); ++i){
			cout << gr[j][i] << " " << gr[j][i + 1] << endl;
		}
	}

	for (int j = 2; j < 3005; ++j)
	{
		if(gr[j].size() > 0){
			cout << gr[j][0] << " " << gr[1][0] << endl;
		}
	}
}

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