#include <bits/stdc++.h>
using namespace std;
pair<int, int> dfs(int x, int p, vector<vector<int>> &AR, int depth)
{
pair<int, int> ans = {depth, x};
for (int i = 0; i < AR[x].size(); i++)
{
if (AR[x][i] == p)
continue;
ans = min(ans, dfs(AR[x][i], x, AR, depth + 1));
}
return ans;
}
pair<int, int> dfs2(int x, int p, vector<vector<int>> &AR, int depth)
{
pair<int, int> ans = {depth / 2, -1};
for (int i = 0; i < AR[x].size(); i++)
{
if (AR[x][i] == p)
continue;
pair<int, int> temp = dfs2(AR[x][i], x, AR, depth + 1);
if (temp.second != -1 && (ans.second == -1 || ans.first < temp.first))
ans = temp;
if (ans.second == -1 && temp.first > ans.first)
ans = temp;
}
if (ans.second == -1 && depth == ans.first)
ans = {depth, x};
return ans;
}
void dfs3(int x, int p, vector<vector<int>> &AR, vector<int> &par)
{
par[x] = p;
for (int i = 0; i < AR[x].size(); i++)
{
if (AR[x][i] == p)
continue;
dfs3(AR[x][i], x, AR, par);
}
}
int main()
{
int N;
cin >> N;
if (N != 100)
return 0;
vector<vector<int>> AR(N);
for (int i = 0; i < N - 1; i++)
{
int a, b;
cin >> a >> b;
AR[a].push_back(b);
AR[b].push_back(a);
}
pair<int, int> far = dfs(0, 0, AR, 0);
pair<int, int> centre = dfs2(far.second, far.second, AR, 1);
int mil = centre.second;
vector<int> p(N);
dfs3(mil, mil, AR, p);
vector<vector<int>> ans1(N), ans2(N);
for (int i = 0; i < N; i++)
{
ans1[i].push_back(i);
ans2[i].push_back(i);
}
vector<int> dist = {3, -12, 27, -56, 88, -100};
for (int i = 0; i < dist.size(); i++)
{
if (dist[i] > 0)
{
for (int j = 0; j < dist[i]; j++)
{
int stop = 1;
for (int k = 0; k < N; k++)
{
ans2[k].push_back(ans2[k][ans2[k].size() - 1]);
ans1[k].push_back(p[ans1[k][ans1[k].size() - 1]]);
if (ans1[k][ans1[k].size() - 1] != mil)
stop = 0;
}
for (int k = 0; k < N; k++)
{
ans2[k].push_back(ans2[k][ans2[k].size() - 1]);
ans1[k].push_back(ans1[k][ans1[k].size() - 1]);
}
// if (stop)
// break;
}
}
else
{
for (int j = 0; j < -dist[i]; j++)
{
int stop = 1;
for (int k = 0; k < N; k++)
{
ans2[k].push_back(ans2[k][ans2[k].size() - 1]);
ans1[k].push_back(ans1[k][ans1[k].size() - 1]);
}
for (int k = 0; k < N; k++)
{
ans2[k].push_back(p[ans2[k][ans2[k].size() - 1]]);
ans1[k].push_back(ans1[k][ans1[k].size() - 1]);
if (ans2[k][ans2[k].size() - 1] != mil)
stop = 0;
}
// if (stop)
// break;
}
}
}
cout << ans1[0].size() - 1 << endl;
for (int i = 0; i < N; i++)
{
for (int j = 1; j < ans1[0].size() - 1; j++)
{
cout << ans1[i][j] << ' ';
}
cout << ans1[i][ans1[i].size() - 1] << '\n';
}
for (int i = 0; i < N; i++)
{
for (int j = 1; j < ans2[0].size() - 1; j++)
{
cout << ans2[i][j] << ' ';
}
cout << ans2[i][ans2[i].size() - 1] << '\n';
}
}
Compilation message
Main.cpp: In function 'std::pair<int, int> dfs(int, int, std::vector<std::vector<int> >&, int)':
Main.cpp:6:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
6 | for (int i = 0; i < AR[x].size(); i++)
| ~~^~~~~~~~~~~~~~
Main.cpp: In function 'std::pair<int, int> dfs2(int, int, std::vector<std::vector<int> >&, int)':
Main.cpp:17:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | for (int i = 0; i < AR[x].size(); i++)
| ~~^~~~~~~~~~~~~~
Main.cpp: In function 'void dfs3(int, int, std::vector<std::vector<int> >&, std::vector<int>&)':
Main.cpp:34:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | for (int i = 0; i < AR[x].size(); i++)
| ~~^~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:67:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for (int i = 0; i < dist.size(); i++)
| ~~^~~~~~~~~~~~~
Main.cpp:73:21: warning: variable 'stop' set but not used [-Wunused-but-set-variable]
73 | int stop = 1;
| ^~~~
Main.cpp:94:21: warning: variable 'stop' set but not used [-Wunused-but-set-variable]
94 | int stop = 1;
| ^~~~
Main.cpp:115:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
115 | for (int j = 1; j < ans1[0].size() - 1; j++)
| ~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:123:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
123 | for (int j = 1; j < ans2[0].size() - 1; j++)
| ~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
1624 KB |
Output is correct |
| 2 |
Correct |
6 ms |
1628 KB |
Output is correct |
| 3 |
Correct |
7 ms |
1628 KB |
Output is correct |
| 4 |
Correct |
7 ms |
1628 KB |
Output is correct |
| 5 |
Correct |
7 ms |
1624 KB |
Output is correct |
| 6 |
Correct |
7 ms |
1624 KB |
Output is correct |
| 7 |
Correct |
8 ms |
1372 KB |
Output is correct |
| 8 |
Correct |
7 ms |
1368 KB |
Output is correct |
| 9 |
Correct |
9 ms |
1372 KB |
Output is correct |
| 10 |
Correct |
7 ms |
1300 KB |
Output is correct |
| 11 |
Correct |
7 ms |
1372 KB |
Output is correct |
| 12 |
Correct |
7 ms |
1368 KB |
Output is correct |
| 13 |
Correct |
11 ms |
1372 KB |
Output is correct |
| 14 |
Correct |
7 ms |
1372 KB |
Output is correct |
| 15 |
Correct |
7 ms |
1372 KB |
Output is correct |
| 16 |
Correct |
7 ms |
1628 KB |
Output is correct |
| 17 |
Correct |
7 ms |
1628 KB |
Output is correct |
| 18 |
Correct |
8 ms |
1628 KB |
Output is correct |
| 19 |
Correct |
7 ms |
1596 KB |
Output is correct |
| 20 |
Correct |
7 ms |
1628 KB |
Output is correct |
| 21 |
Correct |
7 ms |
1628 KB |
Output is correct |
| 22 |
Correct |
7 ms |
1372 KB |
Output is correct |
| 23 |
Correct |
6 ms |
1372 KB |
Output is correct |
| 24 |
Correct |
7 ms |
1600 KB |
Output is correct |
| 25 |
Correct |
8 ms |
1372 KB |
Output is correct |
