oj.uz

답안 #144741

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
144741 2019-08-17T15:42:12 Z emilem Izlet (COI19_izlet) C++14
100 / 100
 963 ms 90368 KB 
#include <algorithm>
#include <iostream>
#include <vector>
#include <set>
using namespace std;

vector< vector<int> > a;
vector< vector<int> > nei, grpNei;
int maxColor = 0;
vector<bool> used;
vector<int> group;
vector<int> color;
vector<bool> met;
vector< vector<int> > groups;

void Dfs(int v, vector<int>& group)
{
	group.push_back(v);
	used[v] = true;
	for (int i = 0; i < nei[v].size(); ++i)
		if (!used[nei[v][i]])
			Dfs(nei[v][i], group);
}
void Tree(int grp)
{
	used[grp] = true;
	for (int i = 0; i < grpNei[grp].size(); ++i)
	{
		int to = grpNei[grp][i];
		if (used[to])
			continue;
		nei[grp].push_back(to);
		nei[to].push_back(grp);
		Tree(to);
	}
}
int FindColor(int grp, int prev, int src)
{
	if (a[groups[src][0]][groups[grp][0]] == a[groups[src][0]][groups[prev][0]] && !met[color[grp]])
		return color[grp];
	met[color[grp]] = true;
	for (int i = 0; i < nei[grp].size(); ++i)
	{
		int to = nei[grp][i];
		if (color[to] != -1 && to != prev)
		{
			int res = FindColor(to, grp, src);
			if (res != -1)
				return res;
		}
	}
	return -1;
}
void Solve(int grp)
{
	fill(met.begin(), met.end(), false);
	for (int i = 0; i < nei[grp].size(); ++i)
		if (color[nei[grp][i]] != -1)
		{
			color[grp] = FindColor(nei[grp][i], grp, grp);
			break;
		}
	if (color[grp] == -1)
		color[grp] = ++maxColor;
	for (int i = 0; i < nei[grp].size(); ++i)
	{
		int to = nei[grp][i];
		if (color[to] == -1)
			Solve(to);
	}
}
void SolveAll()
{
	nei.resize(a.size());
	used.resize(a.size(), false);
	for (int i = 0; i < a.size(); ++i)
		for (int j = 0; j < a.size(); ++j)
			if (a[i][j] == 1 && i != j)
				nei[i].push_back(j);
	for (int i = 0; i < a.size(); ++i)
		if (!used[i])
		{
			groups.push_back(vector<int>());
			Dfs(i, groups.back());
			for (int j = 0; j < groups.back().size(); ++j)
				group[groups.back()[j]] = groups.size() - 1;
		}
	grpNei.resize(groups.size());
	for (int i = 0; i < a.size(); ++i)
		for (int j = 0; j < a.size(); ++j)
			if (a[i][j] == 2 && i != j)
				grpNei[group[i]].push_back(group[j]);
	fill(nei.begin(), nei.end(), vector<int>());
	nei.resize(groups.size());
	fill(used.begin(), used.end(), false);
	used.resize(groups.size());
	Tree(0);
	color.resize(groups.size(), -1);
	met.resize(groups.size());
	Solve(0);
	for (int i = 0; i < a.size(); ++i)
		cout << color[group[i]] << ' ';
	cout << endl;
	for (int i = 0; i < groups.size(); ++i)
		for (int j = 0; j + 1 < groups[i].size(); ++j)
			cout << groups[i][j] + 1 << ' ' << groups[i][j + 1] + 1 << '\n';
	for (int i = 0; i < groups.size(); ++i)
		for (int j = 0; j < nei[i].size(); ++j)
		{
			int to = nei[i][j];
			if (i < to)
				cout << groups[i][0] + 1 << ' ' << groups[to][0] + 1 << '\n';
		}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int subTask;
	cin >> subTask;
	int n;
	cin >> n;
	a.resize(n, vector<int>(n));
	group.resize(n);
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
			cin >> a[i][j];
	SolveAll();

	char I;
	cin >> I;
}
/*
2
5
1 2 2 2 2
2 1 3 3 2
2 3 1 2 3
2 3 2 1 3
2 2 3 3 1
*/

Compilation message

izlet.cpp: In function 'void Dfs(int, std::vector<int>&)':
izlet.cpp:20:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < nei[v].size(); ++i)
                  ~~^~~~~~~~~~~~~~~
izlet.cpp: In function 'void Tree(int)':
izlet.cpp:27:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < grpNei[grp].size(); ++i)
                  ~~^~~~~~~~~~~~~~~~~~~~
izlet.cpp: In function 'int FindColor(int, int, int)':
izlet.cpp:42:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < nei[grp].size(); ++i)
                  ~~^~~~~~~~~~~~~~~~~
izlet.cpp: In function 'void Solve(int)':
izlet.cpp:57:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < nei[grp].size(); ++i)
                  ~~^~~~~~~~~~~~~~~~~
izlet.cpp:65:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < nei[grp].size(); ++i)
                  ~~^~~~~~~~~~~~~~~~~
izlet.cpp: In function 'void SolveAll()':
izlet.cpp:76:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < a.size(); ++i)
                  ~~^~~~~~~~~~
izlet.cpp:77:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < a.size(); ++j)
                   ~~^~~~~~~~~~
izlet.cpp:80:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < a.size(); ++i)
                  ~~^~~~~~~~~~
izlet.cpp:85:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j < groups.back().size(); ++j)
                    ~~^~~~~~~~~~~~~~~~~~~~~~
izlet.cpp:89:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < a.size(); ++i)
                  ~~^~~~~~~~~~
izlet.cpp:90:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < a.size(); ++j)
                   ~~^~~~~~~~~~
izlet.cpp:101:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < a.size(); ++i)
                  ~~^~~~~~~~~~
izlet.cpp:104:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < groups.size(); ++i)
                  ~~^~~~~~~~~~~~~~~
izlet.cpp:105:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j + 1 < groups[i].size(); ++j)
                   ~~~~~~^~~~~~~~~~~~~~~~~~
izlet.cpp:107:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < groups.size(); ++i)
                  ~~^~~~~~~~~~~~~~~
izlet.cpp:108:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < nei[i].size(); ++j)
                   ~~^~~~~~~~~~~~~~~

Subtask #1
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 292 KB Output is correct
2 Correct 796 ms 83624 KB Output is correct
3 Correct 796 ms 83608 KB Output is correct
4 Correct 790 ms 80144 KB Output is correct
5 Correct 786 ms 81228 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 654 ms 36252 KB Output is correct
2 Correct 794 ms 90368 KB Output is correct
3 Correct 901 ms 44744 KB Output is correct
4 Correct 963 ms 44876 KB Output is correct
5 Correct 685 ms 54780 KB Output is correct
6 Correct 725 ms 44740 KB Output is correct
7 Correct 537 ms 36136 KB Output is correct

Subtask #3
57.0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 292 KB Output is correct
2 Correct 796 ms 83624 KB Output is correct
3 Correct 796 ms 83608 KB Output is correct
4 Correct 790 ms 80144 KB Output is correct
5 Correct 786 ms 81228 KB Output is correct
6 Correct 654 ms 36252 KB Output is correct
7 Correct 794 ms 90368 KB Output is correct
8 Correct 901 ms 44744 KB Output is correct
9 Correct 963 ms 44876 KB Output is correct
10 Correct 685 ms 54780 KB Output is correct
11 Correct 725 ms 44740 KB Output is correct
12 Correct 537 ms 36136 KB Output is correct
13 Correct 699 ms 46104 KB Output is correct
14 Correct 880 ms 43352 KB Output is correct
15 Correct 710 ms 55504 KB Output is correct
16 Correct 794 ms 50068 KB Output is correct
17 Correct 885 ms 47684 KB Output is correct
18 Correct 720 ms 46680 KB Output is correct
19 Correct 781 ms 62616 KB Output is correct
20 Correct 706 ms 54524 KB Output is correct
21 Correct 730 ms 55996 KB Output is correct
22 Correct 730 ms 45616 KB Output is correct
23 Correct 685 ms 46328 KB Output is correct
24 Correct 763 ms 44112 KB Output is correct
25 Correct 685 ms 47784 KB Output is correct