oj.uz

Submission #373447

# Submission time Handle Problem Language Result Execution time Memory
373447 2021-03-04T15:48:14 Z pggp Izlet (COI19_izlet) C++14
0 / 100
 2000 ms 53688 KB 
#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 parent[3005];
void un(int x, int y){
	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;
		}
	}
}

void task2(){

}

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 563 ms 53688 KB Output is correct
3 Correct 565 ms 53612 KB Output is correct
4 Execution timed out 2045 ms 53484 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 557 ms 35864 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 563 ms 53688 KB Output is correct
3 Correct 565 ms 53612 KB Output is correct
4 Execution timed out 2045 ms 53484 KB Time limit exceeded
5 Halted 0 ms 0 KB -