oj.uz

Submission #1093373

# Submission time Handle Problem Language Result Execution time Memory
1093373 2024-09-26T17:57:55 Z JuanJL Cezar (COCI16_cezar) C++17
60 / 100
 1 ms 348 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -