1424M - Ancient Language - CodeForces Solution

#include <bits/stdc++.h>

#define FOR(i,a,b) for(register int i=(a);i<(b);++i)

#define ROF(i,a,b) for(register int i=(a);i>=(b);--i)

#define pi pair<int,int>

#define mk(a,b) make_pair(a,b)

#define fi first

#define se second

#define ls(x) ch[x][0]

#define rs(x) ch[x][1]

#define xs(x) (ch[fa[x]][1]==x)

using namespace std;

typedef long long ll;

typedef double db;

typedef long double ldb;

typedef unsigned int ui;

typedef unsigned long long ul;

typedef long long ll;

typedef int n_;

const int maxn = 1005;

const int maxm = 500005;

const int maxlog = 63;

const int inf = 2147483647;

const double eps = 1e-9;

const double E = 2.718281828459;

const double PI = 3.1415926576;

const long long INF = 9223372036854775807ll;

inline ll qpow(ll a,ll b,ll c){register ll ans=1;while(b){if(b&1)ans=ans*a%c;a=a*a%c;b>>=1;}return ans;}

const int mod = 1e9+7;int inv6=qpow(6,mod-2,mod);

inline void dec(n_ &x,n_ y){x-=y,x<0&&(x+=mod);}

inline void add(n_ &x,n_ y){x+=y,x>=mod&&(x-=mod);}

inline n_ sum(n_ x,n_ y){return x+y<mod?x+y:x+y-mod;}

inline n_ sub(n_ x,n_ y){return x-y<0?x-y+mod:x-y;}

inline n_ sqr(n_ x){return 1ll*x*x%mod;}

inline n_ sm1(n_ x){return (1ll*x*(x+1)>>1)%mod;}

inline n_ sm2(n_ x){return 1ll*x*(x+1)%mod*(2*x+1)%mod*inv6%mod;}

inline n_ sm3(n_ x){return 1ll*sqr(x)*sqr(x+1)%mod;}

namespace IO{

	#define getchar() (tt == ss && (tt = (ss = In) + fread(In, 1, 110000000, stdin), ss == tt) ? EOF : *ss++)

	char In[110000000], *ss=In, *tt=In;//In数组要根据输入量更改大小

	const int END = 2147483647;//忽略量

	//整数读入

	inline n_ rd(){//修改一下变量类型即可(int\ll\ul\ui)

		n_ x=0;int fg=1;

		char c=getchar();

		while(c==' ' || c=='\n')c=getchar();

		if(c=='-')fg=-1,c=getchar();

		while(isdigit(c)){

			x=(x<<3)+(x<<1)+(c-48);

			c=getchar();

		}

		return x*fg;

	}

	//字符串读入

	inline int rds(char *s){

		register int len=0;

		register char c=getchar();

		while(c==' ' || c=='\n' || c=='\r')c=getchar();

		while(c!=' ' && c!='\n' && c!='\r' && c!='EOF'){

			s[len++]=c;

			c=getchar();

		}

		return len;

	}

	//读入一行字符串

	inline int getline(char *s){

		register int len=0;

		register char c=getchar();

		while(c==' ' || c=='\n')c=getchar();

		while(c!='\n' && c!='EOF'){

			s[len++]=c;

			c=getchar();

		}

		return len;

	}

	//整数输出

	inline void wr(register n_ x){//不加换行符

		if(x<0)putchar('-'),x=-x;

		if(x>=10)wr(x/10);

		putchar(x%10+'0');

	}

	inline void wrn(register n_ x){//加换行符

		wr(x);

		putchar('\n');

	}

	//正整数格式化输出

	inline void wrd(register n_ x,register int d){//不加换行符

		if(!x){putchar('0');return;}

		register n_ xx =x;

		while(xx)d--,xx/=10;

		FOR(i,0,d)putchar('0');

		wr(x);

	}

	inline void wrdn(register n_ x,register int d){//加换行符

		wrd(x,d);

		putchar('\n');

	}

	//字符串输出

	inline void wrs(const char *s){//不输出换行符

		for(register int i=0;s[i];++i)putchar(s[i]);

	}

	inline void wrsn(const char *s){//输出换行符

		wrs(s);

		putchar('\n');

	}

	inline void debug(const char *s,n_ a=END,n_ b=END,n_ c=END,n_ d=END,n_ e=END,n_ f=END){

		if(s!=NULL)wrs(s),putchar(' ');

		if(a!=END)wr(a),putchar(' ');

		if(b!=END)wr(b),putchar(' ');

		if(c!=END)wr(c),putchar(' ');

		if(d!=END)wr(d),putchar(' ');

		if(e!=END)wr(e),putchar(' ');

		if(f!=END)wr(f),putchar(' ');

		putchar('\n');

	}

}

using namespace IO;



char a[maxn][maxn][102];



int mp[27][27],deg[30],vis[30],len[maxn][maxn],hv[maxn];

vector<int>g[30];

queue<int>q;

int main(){

	int n=rd(),k=rd();

	for(int i=1;i<=n;++i){

		int p=rd();

		hv[p]=1;

		for(int j=0;j<k;++j){

			len[p][j]=rds(a[p][j]);

		}

	}

	int lasti=-1,lastj=-1;

	for(int i=0;i<maxn;++i){

		if(!hv[i])continue;

		for(int j=0;j<k;++j){

			int c=-1;

			for(int h=0;h<len[i][j];++h){

				vis[a[i][j][h]-'a']=1;

				if(lasti!=-1 && h<len[lasti][lastj] && c==-1 && a[i][j][h]!=a[lasti][lastj][h]){

					c=h;

				}

			}

			if(c!=-1){

				int v=a[i][j][c]-'a'+1,u=a[lasti][lastj][c]-'a'+1;

				if(!mp[u][v])g[u].push_back(v),deg[v]++;

				mp[u][v]=1;

				if(mp[v][u]){

					return printf("IMPOSSIBLE\n"),0;

				}

			}else if(lasti!=-1 && len[lasti][lastj]>len[i][j])return printf("IMPOSSIBLE\n"),0;

			lasti=i,lastj=j;

		}

	}

	int tot=0;

	for(int i=1;i<=26;++i){

		if(!vis[i-1])continue;

		if(!deg[i])q.push(i);

		tot++;

	}

	vector<int>ans;

	while(!q.empty()){

		int u=q.front();q.pop();

		ans.push_back(u-1);

		for(auto v:g[u]){

			deg[v]--;

			if(!deg[v])q.push(v);

		}

	}

	if(ans.size()<tot)return printf("IMPOSSIBLE\n"),0;

	for(int i=0;i<ans.size();++i)printf("%c",ans[i]+'a');puts("");

}