LLIAMA3OB

Hidden Supervisors

Aug 1st, 2021 (edited)
1,085
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <algorithm>
  2. #include <array>
  3. #include <iostream>
  4. #include <fstream>
  5. #include <string>
  6. #include <unordered_set>
  7. #include <utility>
  8. #include <vector>
  9.  
  10. using namespace std;
  11.  
  12. const string problemName = "hidden";
  13.  
  14. ifstream fin(problemName + ".in");
  15. ofstream fout(problemName + ".out");
  16. istream& in = fin ? fin : cin;
  17. ostream& out = fin ? fout : cout;
  18.  
  19. // dfs
  20. void numFree(
  21.              size_t u,
  22.              const vector<vector<size_t>>& g,
  23.              vector<bool>& isWinner,
  24.              vector<size_t>& freeNodes) {
  25.     for (auto v : g[u]) {
  26.         numFree(v, g, isWinner, freeNodes);
  27.         if (!isWinner[v]) {
  28.             if (isWinner[u]) {
  29.                 freeNodes.push_back(v);
  30.             } else {
  31.                 isWinner[u] = true;
  32.             }
  33.         }
  34.     }
  35. }
  36.  
  37. int main()
  38. {
  39.     size_t n;
  40.     in >> n;
  41.     vector<vector<size_t>> g(n);
  42.     vector<size_t> roots;
  43.     vector<size_t> ps(n - 1);
  44.     for (size_t i = 1; i != n; ++i) {
  45.         in >> ps[i - 1];
  46.         if (ps[i - 1] != 0) {
  47.             g[ps[i - 1] - 1].push_back(i);
  48.         } else {
  49.             roots.push_back(i);
  50.         }
  51.     }
  52.     vector<bool> isWinner(n);
  53.     // free nodes
  54.     vector<vector<size_t>> v(roots.size());
  55.     for (size_t i = 0; i != roots.size(); ++i) {
  56.         numFree(roots[i], g, isWinner, v[i]);
  57.     }
  58.     vector<size_t> bigBossV;
  59.     numFree(0, g, isWinner, bigBossV);
  60.     // Step 1.
  61.     vector<size_t> loosersRoot;
  62.     for (size_t i = 0; i != roots.size(); ++i) {
  63.         size_t root = roots[i];
  64.         if (isWinner[root]) {
  65.             ps[root - 1] = 1;
  66.             bigBossV.insert(end(bigBossV), begin(v[i]), end(v[i]));
  67.         } else {
  68.             loosersRoot.push_back(i);
  69.         }
  70.     }
  71.     if (!isWinner[0]) {
  72.         bigBossV.push_back(0);
  73.     }
  74.     // Step 2.
  75.     sort(begin(loosersRoot), end(loosersRoot), [&](auto& a, auto& b) {
  76.             return v[a].size() > v[b].size();
  77.          });
  78.     size_t curTree = 0;
  79.     while (!bigBossV.empty() && curTree != loosersRoot.size()) {
  80.         auto rootId = loosersRoot[curTree];
  81.         ps[roots[rootId] - 1] = bigBossV.back() + 1;
  82.         bigBossV.pop_back();
  83.         bigBossV.insert(end(bigBossV), begin(v[rootId]), end(v[rootId]));
  84.         ++curTree;
  85.     }
  86.     // Step 3.
  87.     auto bigBossNumFreeNodes = bigBossV.size();
  88.     if (curTree != loosersRoot.size()) {
  89.         // We have not free nodes in the main (big Boss) tree.
  90.         auto rootId = loosersRoot[curTree];
  91.         if (!v[rootId].empty()) {
  92.             // Here we start step 2, but using rootId tree as main tree.
  93.             v[rootId].push_back(roots[rootId]);
  94.             while (!v[rootId].empty() && ++curTree != loosersRoot.size()) {
  95.                 auto otherRootId = loosersRoot[curTree];
  96.                 ps[roots[otherRootId] - 1] = v[rootId].back();
  97.                 v[rootId].pop_back();
  98.                 v[rootId].insert(end(v[rootId]), begin(v[otherRootId]), end(v[otherRootId]));
  99.             }
  100.             if (curTree != loosersRoot.size()) {
  101.                 // We have not free nodes in rootId tree.
  102.                 // Here all other trees have only one free node (root).
  103.                 while (curTree != loosersRoot.size() && curTree + 1 != loosersRoot.size()) {
  104.                     auto root = roots[loosersRoot[curTree]];
  105.                     ps[roots[loosersRoot[curTree + 1]] - 1] = root + 1;
  106.                     curTree += 2;
  107.                     ps[root - 1] = 1;
  108.                 }
  109.                 if (curTree != loosersRoot.size()) {
  110.                     ps[roots[loosersRoot[curTree]] - 1] = 1;
  111.                     bigBossNumFreeNodes = 1;
  112.                 }
  113.             } else {
  114.                 bigBossNumFreeNodes = v[rootId].size();
  115.             }
  116.             ps[roots[rootId] - 1] = 1;
  117.         } else {
  118.             // Here all other trees have only one free node (root).
  119.             while (curTree != loosersRoot.size() && curTree + 1 != loosersRoot.size()) {
  120.                 auto root = roots[loosersRoot[curTree]];
  121.                 ps[roots[loosersRoot[curTree + 1]] - 1] = root + 1;
  122.                 curTree += 2;
  123.                 ps[root - 1] = 1;
  124.             }
  125.             if (curTree != loosersRoot.size()) {
  126.                 ps[roots[loosersRoot[curTree]] - 1] = 1;
  127.                 bigBossNumFreeNodes = 1;
  128.             }
  129.         }
  130.     }
  131.     // Output.
  132.     out << (n - bigBossNumFreeNodes) / 2 << endl;
  133.     for (auto p : ps) {
  134.         out << p << ' ';
  135.     }
  136.     out << '\n';
  137. }
  138.  
RAW Paste Data