oj.uz

답안 #373452

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
373452 2021-03-04T16:18:32 Z pggp Izlet (COI19_izlet) C++14
43 / 100
 751 ms 74604 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 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -