fork download
copy 
  1. /*
  2.  E. Вирусы
  3.  
  4. Комитет По Исследованию Бинарных Вирусов обнаружил, что некоторые последовательности единиц и нулей являются кодами вирусов. Комитет изолировал набор кодов вирусов. Последовательность из единиц и нулей называется безопасной, если никакой ее подотрезок (т.е. последовательность из соседних элементов) не является кодом вируса. Сейчас цель комитета состоит в том, чтобы установить, существует ли бесконечная безопасная последовательность из единиц и нулей.
  5.  
  6. Указание: используйте алгоритм Ахо-Корасик.
  7.  
  8. Формат ввода
  9. Первая строка входного файла virus.in содержит одно целое число n, равное количеству всех вирусных кодов. Каждая из следующих n строк содержит непустое слово, составленное из символов 0 и 1 — код вируса. Суммарная длина всех слов не превосходит 30 000.
  10.  
  11. Формат вывода
  12. Первая и единственная строка выходного файла должна содержать слово:
  13.  
  14. TAK — если бесконечная, безопасная последовательность из нулей и единиц сушествует;
  15. NIE — в противном случае.
  16.  
  17.  in
  18.  3
  19. 01
  20. 11
  21. 00000
  22.  
  23. out
  24.  NIE
  25.  
  26.  in
  27.  3
  28. 011
  29. 11
  30. 0000
  31.  
  32.  out
  33.  TAK
  34.  
  35.  */
  36.  
  37. #include <ctime>
  38. #include <cstdio>
  39. #include <iostream>
  40. #include <vector>
  41. #include <cstdlib>
  42. #include <set>
  43. #include <string>
  44. #include <unistd.h>
  45.  
  46. using namespace std;
  47.  
  48. struct Vertex {
  49.     string value;
  50.     int suffixLink = 0;
  51.     int parent;
  52.     bool isTerminal = false;
  53.  
  54.     vector<int> childrenId;
  55. };
  56.  
  57. void createSuffixLinks(vector<Vertex> &tree, int id) {
  58.     string letter;
  59.     letter += tree[id].value;
  60.  
  61.     int vertexToCheck = tree[tree[id].parent].suffixLink;
  62.  
  63.     if (vertexToCheck == -1)
  64.         createSuffixLinks(tree, tree[id].parent);
  65.  
  66.     while (vertexToCheck != 0) {
  67.         for (int child : tree[vertexToCheck].childrenId) {
  68.             if (tree[child].value == letter) {
  69.                 tree[id].suffixLink = child;
  70.                 return;
  71.             }
  72.         }
  73.         if (tree[vertexToCheck].suffixLink == -1)
  74.             createSuffixLinks(tree, vertexToCheck);
  75.  
  76.         vertexToCheck = tree[vertexToCheck].suffixLink;
  77.     }
  78.  
  79.     for (int child : tree[0].childrenId) {
  80.         if (tree[child].value == letter) {
  81.             tree[id].suffixLink = child;
  82.             return;
  83.         }
  84.     }
  85.  
  86.     tree[id].suffixLink = 0;
  87.  
  88.     //cout << id << ' ' << tree[id].value << ' ' << tree[id].suffixLink << '\n';
  89. }
  90.  
  91. vector<Vertex> createTree(const vector<string> &lines) {
  92.     setbuf(stdout, nullptr);
  93.     for (string line : lines) {
  94.         cout << line << '\n';
  95.     }
  96.     cout << '\n';
  97.  
  98.     vector<Vertex> tree;
  99.     tree.push_back({"", 0, -1, false});
  100.     int freeId = 1;
  101.  
  102.     for (string line : lines) {
  103.         int parent = 0;
  104.         for (size_t i = 0; i < line.size(); ++i) {
  105.             string letter;
  106.             letter += line[i];
  107.             bool flag = true;
  108.             for (int id : tree[parent].childrenId) {
  109.                 if (tree[id].value == letter) {
  110.                     tree[id].isTerminal = (i == line.size() - 1);
  111.                     parent = id;
  112.                     flag = false;
  113.                     break;
  114.                 }
  115.             }
  116.             if (flag) {
  117.                 tree.push_back({letter, -1, parent, i == line.size() - 1});
  118.                 tree[parent].childrenId.push_back(freeId);
  119.                 parent = freeId;
  120.                 ++freeId;
  121.             }
  122.         }
  123.     }
  124.  
  125.     for (int id : tree[0].childrenId) {
  126.         tree[id].suffixLink = 0;
  127.     }
  128.  
  129.     for (size_t i = 1; i < tree.size(); ++i) {
  130.         if (tree[i].suffixLink == -1) {
  131.             //cout << i << '\n';
  132.             createSuffixLinks(tree, i);
  133.         }
  134.     }
  135.  
  136.     return tree;
  137. }
  138.  
  139. int moveToLetter(const vector<Vertex> &tree, const Vertex &from, const string &letter) {
  140.     for (int child : from.childrenId) {
  141.         if (tree[child].value == letter) {
  142.             return child;
  143.         }
  144.     }
  145.  
  146.     if (from.value.empty())
  147.         return 0;
  148.  
  149.     return moveToLetter(tree, tree[from.suffixLink], letter);
  150. }
  151.  
  152. bool checkCycle(const vector<Vertex> &tree, vector<int> visited, int v) {
  153.     if (tree[v].isTerminal) {
  154.         visited[v] = 2;
  155.         return false;
  156.     }
  157.     // cout << v << '\n';
  158.     visited[v] = 1;
  159.     vector<string> alphabet({"0", "1"});
  160.  
  161.     for (string letter : alphabet) {
  162.         int to = moveToLetter(tree, tree[v], letter);
  163.         if (to == v)
  164.             return true;
  165.  
  166.         if (!visited[to]) {
  167.             if (checkCycle(tree, visited, to))
  168.                 return true;
  169.         } else if (visited[to] == 1) {
  170.             return true;
  171.         }
  172.     }
  173.  
  174.     visited[v] = 2;
  175.     return false;
  176. }
  177.  
  178. void stressTest(int seed) {
  179.     srand(seed);
  180.  
  181.     vector<string> viruses;
  182.     for (int i = 0; i < 4; ++i) {
  183.         string virus;
  184.         for (int j = 0; j < 6
  185.         ; ++j) {
  186.             virus += char('0' + rand() % 2);
  187.         }
  188.         viruses.push_back(virus);
  189.     }
  190.  
  191.     setbuf(stdout, nullptr);
  192.     for (string line : viruses) {
  193.         cout << line << '\n';
  194.     }
  195.     cout << '\n';
  196.  
  197.     vector<Vertex> tree = createTree(viruses);
  198.  
  199.     for (int i = 0; i < tree.size(); ++i)
  200.         cout << i << ' ' << tree[i].value << ' ' << tree[i].suffixLink << '\n';
  201.  
  202.     vector<int> visited(tree.size());
  203.  
  204.     for (int v = 0; v < tree.size(); ++v) {
  205.         if (!visited[v]) {
  206.             if (checkCycle(tree, visited, v)) {
  207.                 cout << "TAK\n";
  208.                 return;
  209.             }
  210.         }
  211.     }
  212.     cout << "NIE\n";
  213. }
  214.  
  215. int main() {
  216.     int virusesCount;
  217.     cin >> virusesCount;
  218.     vector<string> viruses;
  219.     for (int i = 0; i < virusesCount; ++i) {
  220.         string virus;
  221.         cin >> virus;
  222.         viruses.push_back(virus);
  223.     }
  224.  
  225.     vector<Vertex> tree = createTree(viruses);
  226.  
  227.     for (int i = 0; i < tree.size(); ++i)
  228.         cout << i << ' ' << tree[i].value << ' ' << tree[i].suffixLink << '\n';
  229.  
  230.     vector<int> visited(tree.size());
  231.  
  232.     for (int v = 0; v < tree.size(); ++v) {
  233.         if (!visited[v]) {
  234.             if (checkCycle(tree, visited, v)) {
  235.                 cout << "TAK";
  236.                 return 0;
  237.             }
  238.         }
  239.     }
  240.     cout << "NIE";
  241. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
4
000
111
110
001
stdout
copy 
000
111
110
001

0  0
1 0 0
2 0 1
3 0 2
4 1 0
5 1 4
6 1 5
7 0 1
8 1 4
TAK
https://ideone.com/4QbK4C
language:
C++14 (gcc 8.3)
created:
11 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!