| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1274330 | mehrzad | Migrations (IOI25_migrations) | C++17 | 0 ms | 0 KiB |
#include \"migrations.h\"\n#include <bits/stdc++.h>\nusing namespace std;\n\n/* ------- Global data for the first run ------- */\nstatic int Nglob = -1; // number of sites\nstatic int LOG = 0; // log2(N)\nstatic vector<int> depth; // depth of each node\nstatic vector<array<int,15>> up; // binary lifting table (LOG \u2264 15 for N\u226410000)\n\nstatic int a_node = 0, b_node = 0; // current diameter ends\nstatic int diam_len = 0; // current diameter length\n\nstatic int start_idx = 0; // first index from which we start sending messages\nstatic bool dummy_a_sent = false; // have we already sent the dummy for 'a' ?\nstatic bool dummy_b_sent = false; // have we already sent the dummy for 'b' ?\n\n/* ------- Helper functions ------- */\nstatic inline int encode(int nodeIdx, int side) {\n // side = 1 (a) or 2 (b)\n // value is always in [1,20000] because nodeIdx \u2264 9999\n return nodeIdx * 2 + side;\n}\nstatic inline int lca(int u, int v) {\n if (depth[u] < depth[v]) swap(u, v);\n int diff = depth[u] - depth[v];\n for (int k = LOG - 1; k >= 0; --k) {\n if (diff & (1 << k)) u = up[u][k];\n }\n if (u == v) return u;\n for (int k = LOG - 1; k >= 0; --k) {\n if (up[u][k] != -1 && up[u][k] != up[v][k]) {\n u = up[u][k];\n v = up[v][k];\n }\n }\n return up[u][0];\n}\nstatic inline int dist(int u, int v) {\n int w = lca(u, v);\n return depth[u] + depth[v] - 2 * depth[w];\n}\n\n/* ------- The team procedure ------- */\nint send_message(int N, int i, int Pi) {\n // first call: initialise everything\n if (Nglob == -1) {\n Nglob = N;\n LOG = 0;\n while ((1 << LOG) <= N) ++LOG; // LOG \u2264 15 for N = 10000\n depth.assign(N, 0);\n up.assign(N, array<int,15>{});\n for (int k = 0; k < LOG; ++k) up[0][k] = -1;\n a_node = b_node = 0;\n diam_len = 0;\n dummy_a_sent = dummy_b_sent = false;\n start_idx = max(1, N - 50); // we have at most 50 nodes at the end\n }\n\n /* store parent and fill binary lifting table */\n up[i][0] = Pi;\n depth[i] = depth[Pi] + 1;\n for (int k = 1; k < LOG; ++k) {\n int p = up[i][k - 1];\n up[i][k] = (p == -1) ? -1 : up[p][k - 1];\n }\n\n /* update the current diameter */\n int side = 0; // 0 = no change, 1 = a becomes i, 2 = b becomes i\n int new_diam = diam_len;\n int da = dist(i, a_node);\n int db = dist(i, b_node);\n if (da > new_diam) {\n new_diam = da;\n side = 2; // b becomes i\n } else if (db > new_diam) {\n new_diam = db;\n side = 1; // a becomes i\n }\n if (side == 1) a_node = i;\n else if (side == 2) b_node = i;\n diam_len = new_diam;\n\n /* decide what to send */\n if (i < start_idx) return 0; // we send nothing before the tail\n\n int msg = 0;\n\n if (i == start_idx) {\n // first node of the tail: dummy message that tells the current value of a\n msg = encode(a_node, 1);\n dummy_a_sent = true;\n // we deliberately ignore a possible side update here; a will be reported later if it changes again\n } else {\n if (!dummy_b_sent) {\n if (side == 0) {\n // we have a quiet step \u2013 perfect moment to emit dummy for b\n msg = encode(b_node, 2);\n dummy_b_sent = true;\n } else if (i == Nglob - 2) {\n // we are at the second\u2011last node and still have not emitted b.\n // Sacrifice this node to send dummy b; a will still be updated later (at the last node)\n msg = encode(b_node, 2);\n dummy_b_sent = true;\n // side update for a is ignored here.\n } else {\n // normal side update\n msg = encode(i, side);\n if (side == 1) dummy_a_sent = true;\n else dummy_b_sent = true; // side == 2, we have now seen b change\n }\n } else {\n // dummy for b already sent \u2013 just report side updates\n if (side != 0) {\n msg = encode(i, side);\n if (side == 1) dummy_a_sent = true;\n else dummy_b_sent = true;\n } else {\n msg = 0;\n }\n }\n }\n return msg;\n}\n\n/* ------- The museum procedure ------- */\nstd::pair<int,int> longest_path(std::vector<int> S) {\n int a = 0, b = 0;\n for (size_t i = 1; i < S.size(); ++i) {\n int v = S[i];\n if (v == 0) continue;\n int side = (v % 2 == 0) ? 2 : 1; // even \u2192 side 2 (b), odd \u2192 side 1 (a)\n int node = (v - side) / 2;\n if (side == 1) a = node;\n else b = node;\n }\n return {a, b};\n}\n