Submission #133430

#	Time	Username	Problem	Language	Result	Execution time	Memory
133430		Zex	Cezar (COCI16_cezar)	C++11	20 / 100	4 ms	376 KiB

cezar

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define INF INT_MAX
#define output for(int i=0;i<26;i++) { for(int j=0;j<26;j++) { cout << adj[i][j] << " "; }cout<<endl; }cout<<endl;

const int maxN = 101;
int N, M;
vector <int> order(maxN);
vector <string> V(maxN);
int inDegree[26];
bool appearsInInput[26];
bool adj[26][26];
bool valid = true;
vector <int> topoSort;

void findDif( string a, string b, char &_a, char &_b ){

    int len = min( a.length(), b.length() );
    for(int i=0;i<len;i++){
        if( a[i] != b[i] ){
            _a = a[i]; _b = b[i]; return;
        }
    }
    _a = _b = '~';
}

void connect( string a, string b ){

    char _a, _b;
    findDif( a, b, _a, _b );

    if( _a == '~' ) return;

    appearsInInput[_a-97] = appearsInInput[_b-97] = true;
    adj[_a-97][_b-97] = true;
    inDegree[_b-97]++;

}

bool nonValid( string a, string b ){

    if( a.length() <= b.length() ) return false;
    return b == a.substr( 0, b.length() ); // a can never be smaller than b

}

int countDistinct(){

    int rv = 0;
    for(int i=0;i<26;i++) rv += appearsInInput[i];
    return rv;

}

void genTopoSort(){

    queue <int> q;

    while( true ){

        for(int i=0;i<26;i++){
            if( !inDegree[i] && appearsInInput[i] ) q.push(i);
        }

        if( q.empty() ) break;

        int V;
        while( !q.empty() ){

            V = q.front();
            q.pop();
            topoSort.push_back(V);
            inDegree[V] = -1;

            for(int j=0;j<26;j++){
                if( adj[V][j] ) inDegree[j]--;
            }

        }

    }

}

void printRes(){

    cout << "DA" << endl;

    char key[26]; for(int i=0;i<26;i++) key[i] = '~';
    char c = 'a';

    int x;
    for(int i=0;i<topoSort.size();i++){
        x = topoSort[i];
        key[ x ] = c++;
    }
    for(int i=0;i<26;i++) if( key[i] == '~' ) key[i] = c++;

    for(int i=0;i<26;i++) cout << key[i];
    cout << endl;

}

int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    memset( adj, 0, sizeof adj );
    memset( inDegree, 0, sizeof inDegree );
    memset( appearsInInput, 0, sizeof appearsInInput );
    
    cin >> N;
    for(int i=1;i<=N;i++) cin >> V[i];

    for(int i=1;i<=N;i++) cin >> order[i];

    for(int i=1;i<=N;i++){
        for(int j=i+1;j<=N;j++){

            if( nonValid( V[order[i]], V[order[j]] ) ) { valid = false; break; }
            connect( V[order[i]], V[order[j]] );

        } if( !valid ) break;
    }

    M = countDistinct();
    genTopoSort();
    if( topoSort.size() != M ) valid = false;

    if( !valid ) cout << "NE" << endl;
    else printRes();

}

Compilation message (stderr)

cezar.cpp: In function 'void printRes()':
cezar.cpp:94:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<topoSort.size();i++){
                 ~^~~~~~~~~~~~~~~~
cezar.cpp: In function 'int main()':
cezar.cpp:127:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if( topoSort.size() != M ) valid = false;
         ~~~~~~~~~~~~~~~~^~~~

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