Submission #373452

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
373452	2021-03-04T16:18:32 Z	pggp	Izlet (COI19_izlet)	C++14	43 / 100	751 ms	74604 KB

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;

	for (int x = 1; x <= n; ++x)
	{
		for(int i = x - 1; i > 0; i--){
			if(matrix[i][x] == matrix[i][x - 1]){
				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.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	492 KB	Output is correct
2	Correct	591 ms	35820 KB	Output is correct
3	Correct	561 ms	35820 KB	Output is correct
4	Correct	564 ms	35820 KB	Output is correct
5	Correct	582 ms	35820 KB	Output is correct

Subtask #2

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	563 ms	35820 KB	Output is correct
2	Correct	599 ms	53356 KB	Output is correct
3	Correct	736 ms	73708 KB	Output is correct
4	Correct	751 ms	74604 KB	Output is correct
5	Correct	567 ms	53484 KB	Output is correct
6	Correct	616 ms	60652 KB	Output is correct
7	Correct	443 ms	49260 KB	Output is correct

Subtask #3

0 / 57.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	492 KB	Output is correct
2	Correct	591 ms	35820 KB	Output is correct
3	Correct	561 ms	35820 KB	Output is correct
4	Correct	564 ms	35820 KB	Output is correct
5	Correct	582 ms	35820 KB	Output is correct
6	Correct	563 ms	35820 KB	Output is correct
7	Correct	599 ms	53356 KB	Output is correct
8	Correct	736 ms	73708 KB	Output is correct
9	Correct	751 ms	74604 KB	Output is correct
10	Correct	567 ms	53484 KB	Output is correct
11	Correct	616 ms	60652 KB	Output is correct
12	Correct	443 ms	49260 KB	Output is correct
13	Incorrect	581 ms	54252 KB	Unexpected end of file - int32 expected
14	Halted	0 ms	0 KB	-