CodeForces Round 288 Div 2, Problem D

D.C

#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(0);cin.tie(0);

using namespace std;

#define PI acos(-1)
#define sqr(x) ((x) * (x))
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define ALL(c) (c).begin(), (c).end()
#define SIZE(c) (int)(c).size()

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<double,double> dd;

#define PROD //clocking off

/**
 * CodeForces Round 288 Div 2, Problem D
 */

const int MAXN=400000;

map<string, int> vm;

vector<string> ss;
vector<string> sss;
vector< vector<int> > g(MAXN+1);
vector<int> epath;
vector<int> start;

//build euler trail
void build(int s){
	for( ; start[s] < SIZE(g[s]); ){
		int v=g[s][start[s]++];
		build(v);
	}
	epath.PB(s);
}

int main() {
#ifndef PROD
clock_t stop_s,start_s;
start_s=clock();
#endif

	int N, M;
	cin >> N;

	int in_deg[2*N], out_deg[2*N];

	memset(in_deg, 0, 2 * N * sizeof(int));
	memset(out_deg, 0, 2 * N  * sizeof(int));

	for(int i=0;i<N;i++){
		string s;
		cin >> s;
		ss.PB(s);
		string u=s.substr(0,2), v=s.substr(1,2);
		vm[u]=0;
		vm[v]=0;
	}

	//Map the domain of all vertices to the domain of positive integers
	M=0;
	for(map<string,int>::iterator it = vm.begin(); it!=vm.end(); ++it){
		int v=it->S;
		vm[it->F]=M++;
		sss.PB(it->F);
	}

	for(int j=0;j<M;j++){ start.PB(0); }

	for(int i=0;i<N;i++){
		string s=ss[i];
		string s_u=s.substr(0,2), s_v=s.substr(1,2);
		int u=vm[s_u], v=vm[s_v];
		g[u].PB(v);
		in_deg[u]++;
		out_deg[v]++;
	}

	int s=-1, f=-1;
	for(int i=0;i<M;i++){
		if(in_deg[i]==out_deg[i]){ continue; }
		else if(in_deg[i]==out_deg[i]+1){
			if(s>=0){ cout << "NO" << endl; return 0; }
			else{ s=i; }
		}else if(in_deg[i]+1==out_deg[i]){
			if(f>=0){ cout << "NO" << endl; return 0; }
			else{ f=i; }
		}else{ cout << "NO" << endl; return 0; }
	}

	if(f<0){ s=f=0; }
	
	//construct euler trail
	build(s);
		
	if(SIZE(epath)!=N+1){
		cout << "NO" << endl;
		return 0;
	}else{	
		reverse(ALL(epath));

		cout << "YES" << endl;
		cout << sss[epath[0]][0];
		for(int i=0;i<SIZE(epath);i++){ cout << sss[epath[i]][1]; }
		cout << "\n";
	}

#ifndef PROD
stop_s=clock();
cout << "time: " << (stop_s-start_s)/double(CLOCKS_PER_SEC)*1000 << endl;
#endif
	return 0;
}