| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 144728 |
2019-08-17T15:19:20 Z |
emilem |
Izlet (COI19_izlet) |
C++14 |
|
2 ms |
504 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[grp])
return color[grp];
met[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)
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;
if (n == 3000)
throw;
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;
}
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 |
376 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
