# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
416846 | ismoilov | Village (BOI20_village) | C++14 | 5 ms | 5016 KiB |
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;
typedef long long ll;
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define all(x) (x).begin(), (x).end()
#define fp(a,i,c) for(int (a) = (i); (a) < (c); (a)++)
#define fpp(a,i,c) for(int (a) = (i); (a) <= (c); (a)++)
#define fm(a,i,c) for(int (a) = (i); (a) > (c); (a)--)
#define fmm(a,i,c) for(int (a) = (i); (a) >= (c); (a)--)
#define maxx 100010
set <int> g[maxx];
bool vis[maxx];
int amn[maxx];
void S()
{
int n, ans = 0;
cin >> n;
fp(i,1,n){
int x, y;
cin >> x >> y;
x --, y --;
g[x].insert(y);
g[y].insert(x);
amn[i] = i;
}
// cout << endl;
fp(x,0,n){
if(g[x].size() == 1 && vis[x] == 0){
int y;
for(int it : g[x])
y = it;
g[y].erase(x);
g[x].erase(y);
vis[x] = 1, vis[y] = 1;
swap(amn[x], amn[y]);
ans += 2;
//cout << x << " " << y << "first\n";
}
}
bool ok = 1;
while(ok){
ok = 0;
fp(x,0,n){
if(vis[x] == 0){
set <int> d = g[x];
for(int y : d){
if(vis[y] == 1){
g[x].erase(y);
g[y].erase(x);
continue;
}
g[y].erase(x);
g[x].erase(y);
ans += 2;
vis[y] = 1, vis[x] = 1;
swap(amn[x], amn[y]);
ok = 1;
// cout << x << " " << y << "\n";
}
}
/*
if(g[x].size() == 1){
int y;
for(int it : g[x])
y = it;
g[y].erase(x);
g[x].erase(y);
vis[x] = 1, vis[y] = 1;
swap(amn[x], amn[y]);
ok = 1;
ans += 2;
cout << x << " ";
}*/
}
}
cout << ans << "\n";
fp(i,0,n)
cout << amn[i]+1 << " ";
}
int main()
{
IOS;
S();
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |