#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
vector<int> adj[100];
vector<int> path[100];
int dep[100];
int par[100];
void dfs(int x, int p) {
for (auto &y : adj[x]) {
if (y == p) continue;
dep[y] = dep[x] + 1;
par[y] = x;
dfs(y, x);
}
}
vector<pair<int,int>> g[100];
int main() {
ios_base :: sync_with_stdio(false); cin.tie(NULL);
int N;
cin >> N;
if (N != 100) {
//return 0;
}
for (int i=0; i<N-1; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
par[0] = -1;
dfs(0, -1);
int mxdep = 0;
for (int i=0; i<N; i++) {
mxdep = max(mxdep, dep[i]);
g[dep[i]].push_back({i, i});
}
for (int lv=0; lv<2; lv++) {
for (int j=0; j*(1<<lv)<=mxdep; j++) {
if ((j & 1) || !j) {
for (auto &[x, st] : g[j*(1<<lv)]) {
for (int k=0; k<(1<<lv)*2; k++)
path[st].push_back(x);
}
}
else {
for (auto &[x, st] : g[j*(1<<lv)]) {
vector<int> vec;
int t = x;
for (int k=0; k<(1<<lv); k++) {
vec.push_back(par[t]);
path[st].push_back(par[t]);
t = par[t];
}
for (int k=(1<<lv)-2; k>=0; k--) {
path[st].push_back(vec[k]);
}
path[st].push_back(x);
}
}
}
for (int j=0; j*(1<<lv)<=mxdep; j++) {
if (j & 1) {
for (auto &[x, st] : g[j*(1<<lv)]) {
int t = x;
for (int k=0; k<(1<<lv); k++) {
path[st].push_back(par[t]);
t = par[t];
}
g[(j-1)*(1<<lv)].push_back({t, st});
}
}
else {
for (auto &[x, st] : g[j*(1<<lv)]) {
for (int k=0; k<(1<<lv); k++) {
path[st].push_back(x);
}
}
}
}
}
int T = path[0].size() * 2 + 200;
cout << T << '\n';
for (int i=0; i<N; i++) {
for (auto &x : path[i]) {
cout << x << ' ' << x << ' ';
}
for (int j=0; j<200; j++) {
cout << "0 ";
}
cout << '\n';
}
for (int i=0; i<N; i++) {
cout << i << ' ';
for (int j=0; j<path[i].size(); j++) {
cout << path[i][j] << ' ';
if (j + 1 != path[i].size())
cout << path[i][j] << ' ';
}
for (int j=0; j<200; j++) {
cout << "0 ";
}
cout << '\n';
}
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:100:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | for (int j=0; j<path[i].size(); j++) {
| ~^~~~~~~~~~~~~~~
Main.cpp:102:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
102 | if (j + 1 != path[i].size())
| ~~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
344 KB |
Node sequence is invalid |
| 2 |
Halted |
0 ms |
0 KB |
- |
