#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
using namespace std;
int N, in, iix, lcn[303030], deg[303030];
vector<int> leaf[303030], tree[303030], ins;
vector<int> con[303030], inv[303030];
void edge(vector<int> *v, int s, int e){ v[s].push_back(e), v[e].push_back(s); }
void divide(){
for(int i=1; i<=N; i++){
if(deg[i] > N-1-deg[i]) iix=i;
if(deg[i] > 1){
in++, ins.push_back(i);
for(int j=con[i].size(); j--;){
int e=con[i][j];
if(deg[e]==1) leaf[i].push_back(e), lcn[i]++;
else tree[i].push_back(e);
}
}
con[i].clear();
}
}
int tmp[303030], dap;
vector<int> bw[2];
void eachin(int s, int e) { edge(inv, s, e), deg[s]--, deg[e]--, dap++; }
void dfs1(int s, int ix, int col){
tmp[ix]=1;
if(bw[0].size() >= 3 || bw[1].size() >= 3) return;
if(ix!=s) bw[col].push_back(ix);
for(int i=tree[ix].size(); i--;){
int e=tree[ix][i];
if(!tmp[e]) dfs1(s, e, col^1);
}
}
void color_tree(int s){
int left=in-1;
for(int i=tree[s].size(); i--;) tmp[tree[s][i]] = 1;
for(int i=0; i<in; i++){
int e=ins[i];
if(tmp[e]==0 && s!=e) eachin(s, e), left--;
tmp[e]=0;
}
if(left >= 3){
int sz=tree[s].size();
for(int i=0; i<sz; i++){
int a=tree[s][i], b=tree[s][(i+1)%sz];
eachin(a, b);
}
return;
}
dfs1(s, s, 1);
if(left == 1){
if(bw[0].size() >= 2) eachin(bw[0][0], bw[0][1]);
else eachin(bw[1][0], bw[1][1]);
}
else{
eachin(bw[0][0], bw[0][1]);
if(bw[0].size() >= 3) eachin(bw[0][0], bw[0][2]);
else eachin(bw[1][0], bw[1][1]);
}
}
vector<int> lin;
void dfs2(int ix){
tmp[ix]=1;
lin.push_back(ix);
for(int i=tree[ix].size(); i--;){
int e=tree[ix][i];
if(!tmp[e]) dfs2(e);
}
}
void line_tree(int s){
dfs2(s);
int sz=lin.size();
eachin(lin[0], lin[sz-1]);
for(int i=0; i<sz-2; i+=2) eachin(lin[i], lin[i+2]);
for(int i=1; i<sz-2; i+=2) eachin(lin[i], lin[i+2]);
}
struct my {
int sum, ix;
my(int sum_=0, int ix_=0){ sum=sum_, ix=ix_; }
bool operator< (const my &c) const {
return sum < c.sum;
}
};
priority_queue<my> ld, l0, d0;
void push(int s){
my m(lcn[s]+deg[s], s);
if(lcn[s]>0 && deg[s]>0) ld.push(m);
if(lcn[s]==0 && deg[s]>0) l0.push(m);
if(lcn[s]>0 && deg[s]==0) d0.push(m);
}
void eachmatch(int d, int l){
deg[d]--, lcn[l]--;
edge(inv, d, leaf[l][lcn[l]]); dap++;
}
void match(){
for(int i=0; i<in; i++) push(ins[i]);
while(!ld.empty()){
my s=ld.top(), e;
ld.pop();
if(!ld.empty()) e=ld.top(), ld.pop();
else if(!d0.empty()) e=d0.top(), d0.pop();
else e=l0.top(), l0.pop(), swap(s, e);
eachmatch(s.ix, e.ix);
push(s.ix); push(e.ix);
}
while(!l0.empty()){
my s=l0.top(); l0.pop();
my e=d0.top(); d0.pop();
eachmatch(s.ix, e.ix);
push(s.ix); push(e.ix);
}
}
void debug(){
puts("Inner Nodes");
for(int i=0; i<in; i++){
int s=ins[i];
printf("%d: ", s);
for(int j=leaf[s].size(); j--;) printf("%d ", leaf[s][j]);
puts("");
}
puts("Edge");
for(int i=1; i<=N; i++){
for(int j=con[i].size(); j--;) if(i<con[i][j]) printf("%d-%d\n", i, con[i][j]);
}
puts("Anti-Edge");
for(int i=1; i<=N; i++){
for(int j=inv[i].size(); j--;) if(i<inv[i][j]) printf("%d-%d\n", i, inv[i][j]);
}
}
int cjs[303030], ijs[303030];
set<pair<int,int> > sets;
void get_euler(int s, int typ){
if(typ){
while(cjs[s] < con[s].size()){
int e=con[s][cjs[s]++];
if(sets.find(make_pair(s,e)) != sets.end()) continue;
sets.insert(make_pair(s,e)), sets.insert(make_pair(e,s));
get_euler(e, typ^1);
}
}
else{
while(ijs[s] < inv[s].size()){
int e=inv[s][ijs[s]++];
if(sets.find(make_pair(s,e)) != sets.end()) continue;
sets.insert(make_pair(s,e)), sets.insert(make_pair(e,s));
get_euler(e, typ^1);
}
}
printf("%d ", s);
}
int main(){
scanf("%d", &N);
for(int i=0; i<N-1; i++){
int s, e;
scanf("%d%d", &s, &e);
edge(con, s, e);
deg[s]++, deg[e]++;
}
divide();
if(in <= 1){ puts("0"); return 0; }
if(in == 2){
int a=ins[0], b=ins[1];
int mi = min(lcn[a],lcn[b]);
lcn[a]=lcn[b]=deg[a]=deg[b]=mi;
for(int i=0; i<mi; i++){
edge(con, a, leaf[a][i]);
edge(con, b, leaf[b][i]);
}
}
else if(in == 3){
if(iix){
int oth = N-1-deg[iix];
lcn[iix]=oth+1-tree[iix].size(), deg[iix]=oth+1;
}
int a=-1, b=-1, c=-1;
iix = ins[0];
for(int i=0; i<3; i++){
if(deg[iix] < deg[ins[i]]) iix=ins[i];
if(tree[ins[i]].size() == 2) b=ins[i];
else if(a<0) a=ins[i];
else c=ins[i];
}
for(int j=0; j<lcn[a]; j++) edge(con, a, leaf[a][j]);
for(int j=0; j<lcn[b]; j++) edge(con, b, leaf[b][j]);
for(int j=0; j<lcn[c]; j++) edge(con, c, leaf[c][j]);
eachin(a, c);
if(iix==a || iix==b){
deg[a]--, deg[b]--;
edge(con, b, c);
}
if(iix==c){
deg[c]--, deg[b]--;
edge(con, b, a);
}
}
else{
if(iix){
int oth = N-1-deg[iix];
lcn[iix]=oth-tree[iix].size(), deg[iix]=oth;
}
for(int i=0; i<in; i++){
int s=ins[i];
for(int j=0; j<lcn[s]; j++) edge(con, s, leaf[s][j]);
for(int j=tree[s].size(); j--;) con[s].push_back(tree[s][j]);
}
if(in == 4){
for(int i=0; i<in; i++){
int s=ins[i];
for(int j=tree[s].size(); j--;) tmp[tree[s][j]] = 1;
for(int j=i+1; j<in; j++){
if(tmp[ins[j]]==0) eachin(s, ins[j]);
}
for(int j=tree[s].size(); j--;) tmp[tree[s][j]] = 0;
}
}
else{
int lsum=0, ovc=0, ovi;
for(int i=0; i<in; i++) lsum += lcn[ins[i]];
for(int i=0; i<in; i++){
int s=ins[i];
if(deg[s]+lcn[s] > lsum) ovc++, ovi=s;
}
if(ovc==0) ovc=1, ovi=ins[0];
if(ovc==1) color_tree(ovi);
else line_tree(ovi);
}
}
match();
//debug();
printf("%d\n", dap*2);
get_euler(1, 1);
return 0;
}
Compilation message
island.cpp: In function 'void get_euler(int, int)':
island.cpp:150:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(cjs[s] < con[s].size()){
~~~~~~~^~~~~~~~~~~~~~~
island.cpp:158:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(ijs[s] < inv[s].size()){
~~~~~~~^~~~~~~~~~~~~~~
island.cpp: In function 'int main()':
island.cpp:169:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
island.cpp:172:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &s, &e);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
28792 KB |
Correct |
| 2 |
Correct |
26 ms |
28900 KB |
Correct |
| 3 |
Correct |
26 ms |
28900 KB |
Correct |
| 4 |
Correct |
30 ms |
29488 KB |
Correct |
| 5 |
Correct |
26 ms |
29488 KB |
Correct |
| 6 |
Incorrect |
28 ms |
29488 KB |
Unexpected end of file - int32 expected |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
28792 KB |
Correct |
| 2 |
Correct |
26 ms |
28900 KB |
Correct |
| 3 |
Correct |
26 ms |
28900 KB |
Correct |
| 4 |
Correct |
30 ms |
29488 KB |
Correct |
| 5 |
Correct |
26 ms |
29488 KB |
Correct |
| 6 |
Incorrect |
28 ms |
29488 KB |
Unexpected end of file - int32 expected |
| 7 |
Halted |
0 ms |
0 KB |
- |
