Submission #133431

#	Time	Username	Problem	Language	Result	Execution time	Memory
133431		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';
    string vc = "";

    for(int i=0;i<26;i++){
        if( appearsInInput[i] ) vc += char(i+97);
        else key[i] = char(i+97);
    }


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

    sort( vc.begin(), vc.end() );
    int x; int idx = 0;
    for(int i=0;i<topoSort.size();i++){
        int x = topoSort[i];
        key[x] = vc[idx++];
    }

    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:104:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<topoSort.size();i++){
                 ~^~~~~~~~~~~~~~~~
cezar.cpp:109:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(int i=0;i<26;i++) cout << key[i]; cout << endl;
     ^~~
cezar.cpp:109:43: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
     for(int i=0;i<26;i++) cout << key[i]; cout << endl;
                                           ^~~~
cezar.cpp:91:10: warning: unused variable 'c' [-Wunused-variable]
     char c = 'a';
          ^
cezar.cpp:103:9: warning: unused variable 'x' [-Wunused-variable]
     int x; int idx = 0;
         ^
cezar.cpp: In function 'int main()':
cezar.cpp:135: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