oj.uz

Submission #1099903

# Submission time Handle Problem Language Result Execution time Memory
1099903 2024-10-12T05:48:28 Z model_code Sphinx's Riddle (IOI24_sphinx) C++17
100 / 100
 343 ms 3272 KB 
// correct/solution-author-refactor.cpp

#include <bits/stdc++.h>

#include "sphinx.h"
using namespace std;

const int MAX_N = 250 + 10;

const int ACTUAL_COLOR = -1;

using pii = pair<int, int>;

struct ComponentCounter {
  int n;
  vector<vector<int>> adjlist;

  int TT;
  vector<int> seen;

  ComponentCounter(vector<vector<int>> _adjlist)
      : n(_adjlist.size()), adjlist(_adjlist), TT(0), seen(n) {}
  ComponentCounter() : ComponentCounter(vector<vector<int>>()) {}

  /*
   * Marks all vertices in u's connected color component as seen, so long as
   * u's color is constant and known as per proposed_colors.
   *
   * proposed_colors is a list of colors that would be used to query.
   * u is a starting vertex
   */
  // Mark all as seen from u.
  void dfs(vector<int> &proposed_colors, int u) {
    seen[u] = TT;
    for (auto v : adjlist[u]) {
      if (proposed_colors[u] != ACTUAL_COLOR &&
          proposed_colors[u] == proposed_colors[v] && seen[v] != TT) {
        dfs(proposed_colors, v);
      }
    }
  }

  /*
   * Return number of connected color-components among vertices, according to
   * proposed_colors (only among known colors).
   */
  int num_components(vector<int> &proposed_colors, vector<int> &vertices) {
    TT++;
    int ret = 0;
    for (auto u : vertices) {
      if (seen[u] != TT) {
        ret++;
        dfs(proposed_colors, u);
      }
    }
    return ret;
  }
};

struct Groups {
  int n;
  vector<int> groupOf;
  vector<vector<int>> members;

  Groups() : Groups(0) {}
  Groups(int _n) : n(_n), groupOf(_n), members(_n) {
    for (int i = 0; i < n; i++) {
      groupOf[i] = i;
      members[i].push_back(i);
    }
  }

  int group_of(int x) { return groupOf[x]; }

  void join_groups_of(int x, int y) {
    int gx = group_of(x);
    int gy = group_of(y);

    if (members[gx].size() > members[gy].size()) {
      swap(gx, gy);
    }

    for (auto u : members[gx]) {
      groupOf[u] = gy;
      members[gy].push_back(u);
    }
    members[gx].clear();
  }

  vector<int> non_empty_groups() {
    vector<int> res;
    for (int i = 0; i < n; i++) {
      if (!members[i].empty()) {
        res.push_back(i);
      }
    }
    return res;
  }

  // Moves groups to the front
  void compress() {
    auto non_empty_group_indices = non_empty_groups();
    int upto = 0;
    for (auto g : non_empty_group_indices) {
      for (auto u : members[g]) {
        groupOf[u] = upto;
      }
      upto++;
    }
    for (int i = 0; i < n; i++) {
      members[i].clear();
    }
    for (int i = 0; i < n; i++) {
      members[groupOf[i]].push_back(i);
    }
  }

  /*
   * Facilitate a query on the "grouping" graph.
   *
   * This is equivalent to setting all vertices in a group to the group's color.
   * If group's color is ACTUAL_COLOR, then all vertices in the group will be
   * set to ACTUAL_COLOR. Note that this color must be the same for all vertices
   * in that group, since vertices in the same group belong to the same
   * color-connected component.
   *
   * Returns the number of color-connected components.
   * Note that this is always the same in the grouping graph as in the original
   * graph.
   */
  int queryGroups(vector<int> mask) {
    vector<int> proposed_colors(n);
    for (int i = 0; i < n; i++) {
      proposed_colors[i] = mask[groupOf[i]];
    }
    return perform_experiment(proposed_colors);
  }
};

/*
 * Identifies the color-connected components, but not their exact colors.
 */
struct Collapser {
  ComponentCounter componentCounter;
  int n;
  Groups grouper;

  Collapser(ComponentCounter _componentCounter)
      : componentCounter(_componentCounter),
        n(_componentCounter.n),
        grouper(n) {}

  // query for number of components in groups [s, e] union {cur}
  int queryOnly(vector<int> &groups, int s, int e, int cur) {
    vector<int> proposed_colors(n, n);
    for (int i = s; i < e; i++) {
      for (auto u : grouper.members[groups[i]]) {
        proposed_colors[u] = ACTUAL_COLOR;
      }
    }
    proposed_colors[cur] = ACTUAL_COLOR;

    vector<int> others;
    for (int i = 0; i < n; i++) {
      if (proposed_colors[i] == n) {
        others.push_back(i);
      }
    }
    int others_components =
        componentCounter.num_components(proposed_colors, others);

    auto found = perform_experiment(proposed_colors);
    auto res = found - others_components;
    return res;
  }

  // how many edges are from cur to vertices in groups [s, e) ?
  int extra_edges(vector<int> &groups, int s, int e, int cur) {
    auto if_none = e - s + 1;
    auto components = queryOnly(groups, s, e, cur);
    auto edges = if_none - components;
    return edges;
  }

  // there are num_edges edges from cur to vertices in groups [s,e).
  // find them and unionise with cur.
  void solve(vector<int> &groups, int s, int e, int num_edges, int cur) {
    if (num_edges == 0) return;
    if (e - s == num_edges) {
      for (int i = s; i < e; i++) {
        auto u = grouper.members[groups[i]].front();
        grouper.join_groups_of(cur, u);
      }
      return;
    }

    int mid = (e + s) / 2;

    auto left_edges = extra_edges(groups, s, mid, cur);
    solve(groups, s, mid, left_edges, cur);
    solve(groups, mid, e, num_edges - left_edges, cur);
  }

  void go() {
    for (int i = 1; i < n; i++) {
      auto non_empty_groups = grouper.non_empty_groups();
      vector<int> groups;
      for (auto g : non_empty_groups) {
        if (g < i) {
          groups.push_back(g);
        }
      }
      auto edges = extra_edges(groups, 0, groups.size(), i);
      solve(groups, 0, groups.size(), edges, i);
    }
  }

  Groups find_colors() {
    go();
    return grouper;
  }
};

struct TwoColor {
  vector<vector<int>> adjlist;
  vector<int> mark;

  // Defines a connected graph
  TwoColor(vector<vector<int>> _adjlist)
      : adjlist(_adjlist), mark(adjlist.size(), -1) {}

  void dfs(int u) {
    for (auto v : adjlist[u]) {
      if (mark[v] == -1) {
        mark[v] = mark[u] ^ 1;
        dfs(v);
      }
    }
  }

  // Returns a vector which is a 2-coloring of the graph, starting at 0.
  vector<int> two_color() {
    mark[0] = 0;
    dfs(0);
    return mark;
  }
};

// solution to subtask where graph is a coloring
namespace coloring {
Groups grouper;
ComponentCounter componentCounter;
vector<int> proposed_colors;

int known_colors[MAX_N];

// Find all of a particular color in subject, and write it to known_colors, and
// return it. Invariant: at least one of color in subject. Invariant:
// proposed_colors of all of test is color, proposed_colors of all of subject is
// ACTUAL_COLOR (or the actual color). here is number of components for
// proposed_colors
vector<int> find_of_color(int color, vector<int> &subject, vector<int> &test,
                          int here) {
  vector<int> ret;
  if (subject.size() <= 1) {
    for (auto u : subject) {
      known_colors[u] = color;
      ret.push_back(u);
    }
    return ret;
  }

  auto mid = subject.begin() + (subject.size() / 2);
  auto left = vector<int>(subject.begin(), mid);
  auto right = vector<int>(mid, subject.end());

  // check if any on left first
  for (auto u : right) {
    test.push_back(u);
    proposed_colors[u] = color;
  }
  int if_none =
      left.size() + componentCounter.num_components(proposed_colors, test);
  auto actual = grouper.queryGroups(proposed_colors);

  if (actual < if_none) {
    // there's some on the left
    ret = find_of_color(color, left, test, actual);
  }

  for (auto u : right) {
    test.pop_back();
    proposed_colors[u] = ACTUAL_COLOR;
  }

  // check if left accounts for everything
  for (auto u : left) {
    test.push_back(u);
    if (known_colors[u] == color) {
      proposed_colors[u] = color;
    }
  }
  auto test_components = componentCounter.num_components(proposed_colors, test);
  int if_none_right = right.size() + test_components;

  if (here < if_none_right) {
    // there's some on the right
    auto ret_right = find_of_color(color, right, test, here);
    for (auto u : ret_right) {
      ret.push_back(u);
    }
  }
  for (auto u : left) {
    proposed_colors[u] = ACTUAL_COLOR;
    test.pop_back();
  }

  return ret;
}

vector<int> find_colors(Groups _grouper, ComponentCounter _componentCounter,
                        int num_colors) {
  grouper = _grouper;
  componentCounter = _componentCounter;
  int n = componentCounter.n;
  for (int i = 0; i < n; i++) {
    proposed_colors.push_back(ACTUAL_COLOR);
    known_colors[i] = -1;
  }

  if (grouper.non_empty_groups().size() == 1) {
    for (int f = 0; f < num_colors; ++f) {
      vector<int> ord(num_colors, f);
      ord[0] = -1;
      if (perform_experiment(ord) == 1) return {f};
    }
  }

  vector<int> parts[2];
  int comp[2];

  TwoColor twoColor(componentCounter.adjlist);
  auto marks = twoColor.two_color();
  for (int i = 0; i < n; i++) {
    parts[marks[i]].push_back(i);
  }

  for (int z = 0; z < 2; z++) {
    for (auto u : parts[z]) {
      proposed_colors[u] = 0;
    }
    comp[z] = componentCounter.num_components(proposed_colors, parts[z]);
    for (auto u : parts[z]) {
      proposed_colors[u] = ACTUAL_COLOR;
    }
  }

  for (int c = 0; c < num_colors; c++) {
    for (int z = 0; z < 2; z++) {
      for (auto u : parts[z ^ 1]) {
        proposed_colors[u] = c;
      }
      int if_none = parts[z].size() + comp[z ^ 1];
      auto init = grouper.queryGroups(proposed_colors);

      if (init < if_none) {
        find_of_color(c, parts[z], parts[z ^ 1], init);
      }
      for (auto u : parts[z ^ 1]) {
        proposed_colors[u] = ACTUAL_COLOR;
      }
    }
  }

  return vector<int>(known_colors, known_colors + n);
}
}  // namespace coloring

vector<int> find_colours(int n, vector<int> a, vector<int> b) {
  vector<vector<int>> adjlist(n);
  int m = a.size();
  for (int i = 0; i < m; i++) {
    auto u = a[i];
    auto v = b[i];
    adjlist[u].push_back(v);
    adjlist[v].push_back(u);
  }
  ComponentCounter componentCounter(adjlist);

  // Returned solution has the property that every color component has a
  // distinct value. We use this for grouping.
  Collapser collapser(componentCounter);
  auto collapsed_groups = collapser.find_colors();
  collapsed_groups.compress();

  int collapsedNodes = collapsed_groups.non_empty_groups().size();
  vector<vector<int>> collapsedAdjlist(collapsedNodes);
  for (int u = 0; u < collapsedNodes; u++) {
    unordered_set<int> neighbors;
    for (auto uMember : collapsed_groups.members[u]) {
      for (auto vMember : adjlist[uMember]) {
        auto v = collapsed_groups.group_of(vMember);
        if (u != v) {
          neighbors.insert(v);
        }
      }
    }
    for (auto v : neighbors) {
      collapsedAdjlist[u].push_back(v);
    }
  }
  ComponentCounter collapsedCounter(collapsedAdjlist);

  auto groupedColors =
      coloring::find_colors(collapsed_groups, collapsedCounter, n);
  vector<int> known_colors;
  for (int i = 0; i < n; i++) {
    known_colors.push_back(groupedColors[collapsed_groups.group_of(i)]);
  }

  return known_colors;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB #experiments: 13

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB #experiments: 2
2 Correct 1 ms 388 KB #experiments: 5
3 Correct 0 ms 344 KB #experiments: 5
4 Correct 1 ms 344 KB #experiments: 3

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB #experiments: 13
2 Correct 0 ms 344 KB #experiments: 2
3 Correct 1 ms 388 KB #experiments: 5
4 Correct 0 ms 344 KB #experiments: 5
5 Correct 1 ms 344 KB #experiments: 3
6 Correct 1 ms 344 KB #experiments: 74
7 Correct 2 ms 344 KB #experiments: 197
8 Correct 2 ms 344 KB #experiments: 264
9 Correct 3 ms 456 KB #experiments: 231
10 Correct 3 ms 456 KB #experiments: 308
11 Correct 4 ms 344 KB #experiments: 307
12 Correct 3 ms 344 KB #experiments: 366
13 Correct 4 ms 600 KB #experiments: 385
14 Correct 1 ms 344 KB #experiments: 64
15 Correct 4 ms 344 KB #experiments: 254
16 Correct 4 ms 600 KB #experiments: 268
17 Correct 5 ms 344 KB #experiments: 293
18 Correct 5 ms 344 KB #experiments: 333
19 Correct 5 ms 508 KB #experiments: 343
20 Correct 5 ms 344 KB #experiments: 366
21 Correct 6 ms 600 KB #experiments: 385
22 Correct 3 ms 344 KB #experiments: 292
23 Correct 5 ms 344 KB #experiments: 280
24 Correct 4 ms 344 KB #experiments: 311
25 Correct 5 ms 344 KB #experiments: 356
26 Correct 4 ms 344 KB #experiments: 273
27 Correct 5 ms 344 KB #experiments: 326
28 Correct 5 ms 596 KB #experiments: 368
29 Correct 5 ms 344 KB #experiments: 305
30 Correct 4 ms 476 KB #experiments: 354
31 Correct 4 ms 496 KB #experiments: 290
32 Correct 5 ms 344 KB #experiments: 351
33 Correct 2 ms 344 KB #experiments: 112
34 Correct 7 ms 344 KB #experiments: 385

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB #experiments: 2
2 Correct 1 ms 388 KB #experiments: 5
3 Correct 0 ms 344 KB #experiments: 5
4 Correct 1 ms 344 KB #experiments: 3
5 Correct 1 ms 344 KB #experiments: 74
6 Correct 2 ms 344 KB #experiments: 197
7 Correct 2 ms 344 KB #experiments: 264
8 Correct 3 ms 456 KB #experiments: 231
9 Correct 3 ms 456 KB #experiments: 308
10 Correct 4 ms 344 KB #experiments: 307
11 Correct 3 ms 344 KB #experiments: 366
12 Correct 4 ms 600 KB #experiments: 385
13 Correct 19 ms 600 KB #experiments: 851
14 Correct 22 ms 600 KB #experiments: 988
15 Correct 35 ms 488 KB #experiments: 1449
16 Correct 33 ms 508 KB #experiments: 1431
17 Correct 62 ms 500 KB #experiments: 1921
18 Correct 69 ms 496 KB #experiments: 2175
19 Correct 70 ms 528 KB #experiments: 2359
20 Correct 8 ms 520 KB #experiments: 383
21 Correct 67 ms 592 KB #experiments: 2493

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB #experiments: 2
2 Correct 1 ms 388 KB #experiments: 5
3 Correct 0 ms 344 KB #experiments: 5
4 Correct 1 ms 344 KB #experiments: 3
5 Correct 1 ms 344 KB #experiments: 64
6 Correct 4 ms 344 KB #experiments: 254
7 Correct 4 ms 600 KB #experiments: 268
8 Correct 5 ms 344 KB #experiments: 293
9 Correct 5 ms 344 KB #experiments: 333
10 Correct 5 ms 508 KB #experiments: 343
11 Correct 5 ms 344 KB #experiments: 366
12 Correct 6 ms 600 KB #experiments: 385
13 Correct 58 ms 1956 KB #experiments: 997
14 Correct 100 ms 1880 KB #experiments: 1401
15 Correct 138 ms 1880 KB #experiments: 1709
16 Correct 158 ms 1960 KB #experiments: 1923
17 Correct 178 ms 1880 KB #experiments: 2194
18 Correct 164 ms 1960 KB #experiments: 2304
19 Correct 234 ms 2212 KB #experiments: 2397
20 Correct 21 ms 2132 KB #experiments: 309
21 Correct 343 ms 3272 KB #experiments: 2493

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB #experiments: 13
2 Correct 0 ms 344 KB #experiments: 2
3 Correct 1 ms 388 KB #experiments: 5
4 Correct 0 ms 344 KB #experiments: 5
5 Correct 1 ms 344 KB #experiments: 3
6 Correct 1 ms 344 KB #experiments: 74
7 Correct 2 ms 344 KB #experiments: 197
8 Correct 2 ms 344 KB #experiments: 264
9 Correct 3 ms 456 KB #experiments: 231
10 Correct 3 ms 456 KB #experiments: 308
11 Correct 4 ms 344 KB #experiments: 307
12 Correct 3 ms 344 KB #experiments: 366
13 Correct 4 ms 600 KB #experiments: 385
14 Correct 1 ms 344 KB #experiments: 64
15 Correct 4 ms 344 KB #experiments: 254
16 Correct 4 ms 600 KB #experiments: 268
17 Correct 5 ms 344 KB #experiments: 293
18 Correct 5 ms 344 KB #experiments: 333
19 Correct 5 ms 508 KB #experiments: 343
20 Correct 5 ms 344 KB #experiments: 366
21 Correct 6 ms 600 KB #experiments: 385
22 Correct 3 ms 344 KB #experiments: 292
23 Correct 5 ms 344 KB #experiments: 280
24 Correct 4 ms 344 KB #experiments: 311
25 Correct 5 ms 344 KB #experiments: 356
26 Correct 4 ms 344 KB #experiments: 273
27 Correct 5 ms 344 KB #experiments: 326
28 Correct 5 ms 596 KB #experiments: 368
29 Correct 5 ms 344 KB #experiments: 305
30 Correct 4 ms 476 KB #experiments: 354
31 Correct 4 ms 496 KB #experiments: 290
32 Correct 5 ms 344 KB #experiments: 351
33 Correct 2 ms 344 KB #experiments: 112
34 Correct 7 ms 344 KB #experiments: 385
35 Correct 19 ms 600 KB #experiments: 851
36 Correct 22 ms 600 KB #experiments: 988
37 Correct 35 ms 488 KB #experiments: 1449
38 Correct 33 ms 508 KB #experiments: 1431
39 Correct 62 ms 500 KB #experiments: 1921
40 Correct 69 ms 496 KB #experiments: 2175
41 Correct 70 ms 528 KB #experiments: 2359
42 Correct 8 ms 520 KB #experiments: 383
43 Correct 67 ms 592 KB #experiments: 2493
44 Correct 58 ms 1956 KB #experiments: 997
45 Correct 100 ms 1880 KB #experiments: 1401
46 Correct 138 ms 1880 KB #experiments: 1709
47 Correct 158 ms 1960 KB #experiments: 1923
48 Correct 178 ms 1880 KB #experiments: 2194
49 Correct 164 ms 1960 KB #experiments: 2304
50 Correct 234 ms 2212 KB #experiments: 2397
51 Correct 21 ms 2132 KB #experiments: 309
52 Correct 343 ms 3272 KB #experiments: 2493
53 Correct 60 ms 552 KB #experiments: 2007
54 Correct 64 ms 616 KB #experiments: 2036
55 Correct 107 ms 628 KB #experiments: 2056
56 Correct 66 ms 660 KB #experiments: 2036
57 Correct 168 ms 1612 KB #experiments: 1642
58 Correct 241 ms 1624 KB #experiments: 2096
59 Correct 204 ms 1588 KB #experiments: 1881
60 Correct 313 ms 1632 KB #experiments: 2405
61 Correct 47 ms 488 KB #experiments: 1648
62 Correct 57 ms 508 KB #experiments: 2033
63 Correct 63 ms 600 KB #experiments: 2352
64 Correct 73 ms 600 KB #experiments: 1972
65 Correct 55 ms 608 KB #experiments: 1991
66 Correct 73 ms 620 KB #experiments: 2049
67 Correct 57 ms 616 KB #experiments: 2039
68 Correct 65 ms 636 KB #experiments: 1944
69 Correct 76 ms 636 KB #experiments: 2010
70 Correct 97 ms 636 KB #experiments: 2033
71 Correct 66 ms 644 KB #experiments: 1929
72 Correct 58 ms 592 KB #experiments: 1990
73 Correct 59 ms 560 KB #experiments: 1952
74 Correct 66 ms 600 KB #experiments: 2053
75 Correct 72 ms 612 KB #experiments: 1961
76 Correct 89 ms 620 KB #experiments: 2011
77 Correct 80 ms 632 KB #experiments: 1953
78 Correct 73 ms 660 KB #experiments: 1999
79 Correct 77 ms 676 KB #experiments: 1921
80 Correct 73 ms 696 KB #experiments: 1990
81 Correct 66 ms 680 KB #experiments: 1993
82 Correct 136 ms 988 KB #experiments: 2369
83 Correct 146 ms 1368 KB #experiments: 1819
84 Correct 340 ms 2252 KB #experiments: 2384
85 Correct 18 ms 600 KB #experiments: 470
86 Correct 266 ms 1504 KB #experiments: 2493