oj.uz

Submission #91176

# Submission time Handle Problem Language Result Execution time Memory
91176 2018-12-26T12:50:41 Z nikolapesic2802 Cezar (COCI16_cezar) C++14
40 / 100
 3 ms 672 KB 
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <cstring>
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 110;
const int SLOVA = 26;
const int N=26;
int mat[SLOVA][SLOVA];

vector<int> graf[MAXN];

int n;

string unos[MAXN], glavni[MAXN];

int in[SLOVA];

int bio[SLOVA];

vector<int> ispis;

int lcp(int a, int b)
{
  int kraj = min((int)glavni[a].size(), (int)glavni[b].size());
  int i = 0;
  for(; i < kraj; i++)
    if(glavni[a][i] != glavni[b][i]) 
      break;
  return i;
}

int pref(int a, int b)
{
  int x = lcp(a, b);
  if(x == (int)glavni[a].size()) return 1;
  return 0;
}

void dodaj(int x, int y)
{
  if(mat[x][y]) return;
  mat[x][y] = 1;
  graf[x].push_back(y);
  in[y]++;
}

int da;

void rek(int cvor)
{
  if(bio[cvor])
  {
    da = 1;
    return;
  }
  bio[cvor] = 1;
  for(int i = 0; i < (int) graf[cvor].size(); i++)
    rek(graf[cvor][i]);
  bio[cvor] = 0;
}

void topoloski(int cvor)
{
  if(bio[cvor]) return;
  bio[cvor] = 1;
  for(int i = 0; i < (int)graf[cvor].size(); i++)
    topoloski(graf[cvor][i]);
  ispis.push_back(cvor);
}

int main()
{
  cin >> n;
  for(int i = 0; i < n; i++)
    cin >> unos[i];
  for(int i = 0; i < n; i++)
  {
    int x;
    cin >> x;
    x--;
    glavni[i] = unos[x];
  }
  for(int i = 0; i < n; i++)
    for(int j = 0; j < i; j++)
      if(pref(i, j))
      {
        cout << "NE" << endl;
        return 0;
      }
  for(int i = 0; i < n - 1; i++)
  {
    if(pref(i, i + 1)) continue;
    for(int j = 0; ; j++)
    {
      if(glavni[i][j] != glavni[i + 1][j])
      {
        dodaj(glavni[i][j] - 'a', glavni[i+1][j] - 'a');
        break;
      }
    }
  }
  int tr=0;
    vector<int> degree(N);
    for(int i=0;i<N;i++)
    {
        for(auto p:graf[i])
        {
            degree[p]++;
        }
    }
    vector<int> sol(N,-1);
    for(int i=0;i<N;i++)
    {
        bool ima=false;
        for(int j=0;j<N;j++)
        {
            if(degree[j]==0)
            {
                sol[j]=tr;
                tr++;
                ima=true;
                for(auto p:graf[j])
                {
                    degree[p]--;
                }
                degree[j]=INT_MAX;
                break;
            }
        }
        if(!ima)
        {
            printf("NE\n");
            return 0;
        }
    }
    printf("DA\n");
    for(int i=0;i<N;i++)
    {
        printf("%c",sol[i]+'a');
    }
    printf("\n");
    return 0;
  for(int i = 0; i < SLOVA; i++)
  {
    memset(bio, 0, sizeof(bio));
    da = 0;
    rek(i);
    if(da)
    {
      cout << "NE" << endl;
      return 0;
    }
  }
  memset(bio, 0, sizeof(bio));
  for(int i = 0; i < SLOVA; i++)
    if(!in[i])
      topoloski(i);
  cout << "DA" << endl;
  int rj[MAXN];
  for(int i = 0; i < (int)ispis.size(); i++)
    rj[ispis[i]] = i;
  for(int i = 0; i < SLOVA; i++)
    cout << (char)(rj[i] + 'a');
  cout << endl;
  return 0;
}

Subtask #1
0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 548 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 2 ms 548 KB Output is correct
2 Correct 2 ms 548 KB Output is correct

Subtask #7
10.0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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