This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
mt19937 rng((uint32_t) chrono::steady_clock::now().time_since_epoch().count());
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T>
using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T>
using indexed_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T>
void print(T a) {
for (auto i : a) {
cout << i << " ";
}
cout << "\n";
}
void setIO() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef DEBUG
//freopen("solution.out", "w", stdout);
freopen("3.in", "r", stdin);
#endif
}
const int maxn = 1e5 + 1;
vector<int> adj[maxn];
int deg[maxn], pos[maxn];
int main() {
setIO();
int n;
cin >> n;
int a, b;
for (int i = 0; i < n - 1; ++i) {
cin >> a >> b;
--a, --b;
adj[a].push_back(b);
adj[b].push_back(a);
++deg[a], ++deg[b];
pos[i] = i;
}
pos[n - 1] = n - 1;
unordered_set<int> leafs;
for (int i = 0; i < n; ++i) {
if (deg[i] == 1) {
leafs.insert(i);
}
}
int sol = 0;
while (!leafs.empty()) {
int cur = *leafs.begin();
cout << cur << endl;
leafs.erase(leafs.begin());
int next = adj[cur][0];
if (pos[cur] == cur) {
sol += 2;
swap(pos[cur], pos[next]);
}
if (--deg[next] == 1) {
leafs.insert(adj[cur][0]);
}
adj[next].erase(find(adj[next].begin(), adj[next].end(), cur));
}
cout << sol << " " << 1 << "\n";
vector<int> loc(n);
for (int i = 0; i < n; ++i) {
loc[pos[i]] = i;
assert(pos[i] != i);
}
for (int i = 0; i < n - 1; ++i) {
cout << loc[i] + 1 << " ";
}
cout << loc[n - 1] + 1 << "\n";
for (int i = 0; i < n - 1; ++i) {
cout << 1 << " ";
}
cout << 1 << "\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |