Advertisement
Sanlover

Untitled

Apr 14th, 2022
946
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.27 KB | None | 0 0
  1. #include <iostream>
  2. #include <stack>
  3. #include <vector>
  4. using namespace std;
  5.  
  6. vector<vector<size_t>> tree;
  7. vector<stack<size_t>> stackTmp;
  8. vector<size_t> colors, result;
  9.  
  10. // Реализация алгоритма описанного в документе
  11. // -1  - нет соседа под условие
  12. void taskDfs(const size_t& v)
  13. {
  14.     const int currentColor = colors[v];
  15.     result[v] = stackTmp[currentColor].empty() ? -1 : stackTmp[currentColor].top();
  16.  
  17.     stackTmp[currentColor].push(v);
  18.     for (size_t i = 0; i < tree[v].size(); i++)
  19.     {
  20.         taskDfs(tree[v][i]);
  21.     }
  22.     stackTmp[currentColor].pop();
  23. }
  24.  
  25. int main()
  26. {
  27.     size_t n, c, tmp;
  28.  
  29.     // Считываем начальные данные
  30.     cin >> n >> c;
  31.     tree.resize(n + 1);
  32.  
  33.     // Потом считываем 2 строку
  34.     for (size_t i = 2; i <= n; i++)
  35.     {
  36.         cin >> tmp;
  37.         tree[tmp].push_back(i);
  38.     }
  39.     colors.resize(n + 1);
  40.  
  41.     // Потом считываем 3 строку
  42.     for (size_t i = 1; i <= n; i++)
  43.     {
  44.         cin >> colors[i];
  45.     }
  46.     stackTmp.resize(c + 1);
  47.     result.resize(n + 1);
  48.  
  49.     // Запускаем наш метод
  50.     taskDfs(1);
  51.  
  52.  
  53.     // Выводим результат
  54.     cout << endl << "Results:" << endl;
  55.     for (size_t i = 1; i <= n; i++)
  56.     {
  57.         cout << result[i] << " ";
  58.     }
  59.     return 0;
  60. }
  61.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement