Submission #68817

#	Time	Username	Problem	Language	Result	Execution time	Memory
68817		imsifile	Island Traversal (FXCUP3_island)	C++98	0 / 100	35 ms	29300 KiB

island

#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;
		sort(leaf[a].begin(), leaf[a].end());
		sort(leaf[b].begin(), leaf[b].end());
		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];
			sort(leaf[iix].begin(), leaf[iix].end());
			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];
			sort(leaf[iix].begin(), leaf[iix].end());
			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 (stderr)

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);
   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 42
• Subtask 2: 0 / 58