Submission #1093373

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093373		JuanJL	Cezar (COCI16_cezar)	C++17	60 / 100	1 ms	348 KiB

cezar

#include <bits/stdc++.h>

using namespace std;


#define pb push_back
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
#define fst first
#define snd second
#define forn(i,a,b) for(int i = a; i < b; i++)
#define mset(a,v) memset(a,v,sizeof(a))
typedef long long ll;

const int MAXL = 27;
const int MAXN = 100+5;

bool adj[MAXL][MAXL];
bool visited[MAXN];
bool nvis[MAXN];
bool cycle = false;

void detect_cycle(ll nd ){
	if(nvis[nd]){ cycle = true; return; }
	if(visited[nd]) return;
	nvis[nd] = true;
	visited[nd] = true;
	forn(i,0,MAXL) if(adj[nd][i]){
		detect_cycle(i);
	}
	nvis[nd] = false;
	return;
}


vector<ll> topo;

void toposort(ll nd){
	if(visited[nd]) return;
	visited[nd]=true;
	forn(i,0,MAXL) if(adj[nd][i]){
		toposort(i);
	}
	topo.pb(nd);
}
	
	

int main(){
	bool ok = true;
	ll n; cin>>n;
	vector<string> strs(n);
	vector<ll> ord(n);
	forn(i,0,n) cin>>strs[i];
	forn(i,0,n) cin>>ord[i];
	vector<pair<ll,string>> sorted;
	forn(i,0,n){
		sorted.pb({i,strs[ord[i]-1]});
	}
	sort(ALL(sorted));
	forn(i,0,n){
		forn(j,i+1,n){
			string a,b; a = sorted[i].snd; b = sorted[j].snd;
			bool difiere = false;
			forn(h,0,min(SZ(a),SZ(b))){
				if(a[h]!=b[h]){
					difiere=true;
					//cout <<b[h]<<" "<<a[h]<<'\n';
					adj[b[h]-'a'][a[h]-'a']=true;
					break;
				}
			}
			if(!difiere){
				if(SZ(a)>=SZ(b)){
					ok=false;
				}
			}
		}
	}
	forn(i,0,27){
		detect_cycle(i);
	}
	if(cycle || !ok){
		cout<<"NE\n";
	}else{
		mset(visited,0);
		forn(i,0,26){
			if(!visited[i]) toposort(i);
		}
		//cout<<SZ(topo)<<'\n';
		cout<<"DA\n";
		ll last = 0;
		vector<char> dic(26,'-');
		forn(i,0,SZ(topo)){
			dic[topo[i]]='a'+i;
			last = i;
		}
		for(auto i:dic) cout<<i; cout<<'\n';
	}
					
	return 0;
}

Compilation message (stderr)

cezar.cpp: In function 'int main()':
cezar.cpp:98:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   98 |   for(auto i:dic) cout<<i; cout<<'\n';
      |   ^~~
cezar.cpp:98:28: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   98 |   for(auto i:dic) cout<<i; cout<<'\n';
      |                            ^~~~
cezar.cpp:92:6: warning: variable 'last' set but not used [-Wunused-but-set-variable]
   92 |   ll last = 0;
      |      ^~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10