| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 144741 |
2019-08-17T15:42:12 Z |
emilem |
Izlet (COI19_izlet) |
C++14 |
|
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)
~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
