Advertisement

# IOI '18 - Doll (53pts)

Jul 27th, 2022
591
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include "doll.h"
2. #include <set>
3. #include <tuple>
4. #include <cassert>
5. #include <iostream>
6.
7. using namespace std;
8.
9. const int INF = 1e9;
10.
11. bool drain(int i, int root, vector<int> &X, vector<int> &Y) {
12.   bool isDrain = false;
13.   if (X[-i] < 0) {if (drain(X[-i], root, X, Y)) isDrain = true;}
14.   else if (X[-i] == 0 || X[-i] == INF) X[-i] = root, isDrain = true;
15.   if (Y[-i] < 0) {if (drain(Y[-i], root, X, Y)) isDrain = true;}
16.   else if (Y[-i] == 0 || Y[-i] == INF) Y[-i] = root, isDrain = true;
17.   return isDrain;
18. }
19.
20. void create_circuit(int M, vector<int> A) {
21.   int N = A.size();
22.   vector<vector<int>> nxt(1+M);
23.   nxt[0].push_back(A[0]);
24.   for (int i = 0; i < N-1; ++i) {
25.     nxt[A[i]].push_back(A[i+1]);
26.   }
27.   nxt[A[N-1]].push_back(0);
28.
29.   int S = 0;
30.   vector<int> X(1), Y(1);
31.   vector<int> C(1+M); // root switch for each trigger
32.
33.   for (int i = 0; i <= M; ++i) {
34.     if (nxt[i].empty()) { // unused trigger
35.       C[i] = i;
36.       continue;
37.     }
38.     int p2 = 1, expo = 0;
39.     while (p2 < (int)nxt[i].size()) ++expo, p2 <<= 1;
40.
41.     // Order targets (stored in nxt) for tree of switches
42.     vector<int> orderedNxt(1, 0);
43.     for (int j = 1, previousPow2 = 1; j <= expo; ++j, previousPow2 <<= 1) {
44.       vector<int> nextLevel(2*orderedNxt.size());
45.       for (int k = 0; k < (int)nextLevel.size(); ++k) {
46.         nextLevel[k] = orderedNxt[k>>1] + (k&1)*previousPow2;
47.       }
48.       orderedNxt = nextLevel;
49.     }
50.     for (int j = 0; j < p2; ++j) {
51.       if (orderedNxt[j] >= (int)nxt[i].size()) orderedNxt[j] = INF;
52.       else orderedNxt[j] = nxt[i][orderedNxt[j]];
53.     }
54.
55.     // Now build switches for pairs of targets
56.     vector<int> curSwitches = orderedNxt;
57.     while (curSwitches.size() > 1) {
58.       vector<int> nextSwitches((int)curSwitches.size()>>1);
59.       for (int j = 0; j < (int)nextSwitches.size(); ++j) {
60.         int x = curSwitches[2*j], y = curSwitches[2*j+1];
61.         if (x==INF && y==INF) {// this should never happen
62.           nextSwitches[j] = INF;
63.           continue;
64.         }
65.         // create switch
66.
67.         // Create new switch
68.         ++S;
69.         X.push_back(x);
70.         Y.push_back(y);
71.         nextSwitches[j] = -S;
72.       }
73.       curSwitches = nextSwitches;
74.     }
75.
76.     // now curSwitches[0] is the root switch for this trigger
77.     C[i] = curSwitches[0];
78.   }
79.
80.   // Now we need to "drain" the switches at the end so they all have state X at the end
81.   //  find the roots of the trees that need draining
82.   vector<int> needDrain;
83.   for (int i = 0; i <= M; ++i) {
84.     if (C[i] >= 0) {
85.       if (C[i] == 0 || C[i] == INF) C[i] = i;
86.     } else if (drain(C[i], C[i], X, Y) && i != A[N-1]) {
87.       needDrain.push_back(i);
88.     }
89.   }
90.
91.   auto getBottom = [&C, &Y](int i) {
92.     int root = C[i]; i = C[i];
93.     while (true) {
94.       if (i > 0) {
95.         if (C[i] == root) return i;
96.         i = C[i];
97.       } else {
98.         if (Y[-i] == root) return i;
99.         i = Y[-i];
100.       }
101.     }
102.   };
103.
104.   //  link up the drain chain drain chain
105.   int prevBottom = getBottom(A[N-1]);
106.   for (int i : needDrain) {
107.     // connect bottom (end) of previous to root of current
108.     if (prevBottom > 0) C[prevBottom] = C[i];
109.     else Y[-prevBottom] = C[i];
110.     // find bottom of current
111.     prevBottom = getBottom(i);
112.   }
113.
114.   //   connect last bottom back to the origin
115.   if (prevBottom > 0) C[prevBottom] = 0;
116.   else Y[-prevBottom] = 0;
117.
118.   X.erase(X.begin());
119.   Y.erase(Y.begin());
120.   answer(C, X, Y);
121. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement