oj.uz

Submission #1099898

# Submission time Handle Problem Language Result Execution time Memory
1099898 2024-10-12T05:47:29 Z model_code Sphinx's Riddle (IOI24_sphinx) C++17
100 / 100
 345 ms 3252 KB 
// correct/solution-author.cpp

#include <bits/stdc++.h>

#include "sphinx.h"
using namespace std;

#ifdef DEBUG
#define D(x...) fprintf(stderr, x)
#define DA(x) assert(x)
#else
#define D(x...)
#define DA(x)
#endif

const int MAX_N = 250 + 10;

const int ACTUAL_COLOR = -1;

using pii = pair<int, int>;

// solution to subtask where you just need to identify the color-connected
// components
namespace collapse {
int n;
vector<int> adjlist[MAX_N];
vector<int> proposed_colors;

namespace components {
int TT;
int seen[MAX_N];

// Mark all as seen from u.
void dfs(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(v);
    }
  }
}

// Return number of components in a vector
int num_components(vector<int> &vertices) {
  TT++;
  int ret = 0;
  for (auto u : vertices) {
    if (seen[u] != TT) {
      ret++;
      dfs(u);
    }
  }
  return ret;
}
}  // namespace components

namespace forest {
int ugroup[MAX_N];
vector<int> members[MAX_N];

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

int get(int x) { return ugroup[x]; }

void join(int x, int y) {
  int gx = get(x);
  int gy = get(y);

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

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

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

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

  auto found = perform_experiment(proposed_colors);
  auto res = found - others_components;
  D("queryOnly %d: found %d, others components = %d\n", 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;
  D("extra_edges=%d for [%d, %d) with cur=%d: if_none=%d, components=%d\n",
    edges, s, e, cur, 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) {
  D("solve([");
  for (int i = s; i < e; i++) {
    D("%d ", groups[i]);
  }
  D("], num_edges=%d, cur=%d)\n", num_edges, cur);

  DA(num_edges <= e - s);
  if (num_edges == 0) return;
  if (e - s == num_edges) {
    for (int i = s; i < e; i++) {
      auto u = members[groups[i]].front();
      D("! identified that %d and %d are in the same color component\n", cur,
        u);
      join(cur, u);
    }
    return;
  }

  DA(e - s > 1);
  int mid = (e + s) / 2;

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

void go() {
  for (int i = 0; i < n; i++) {
    ugroup[i] = i;
    members[i].push_back(i);
  }

  for (int i = 1; i < n; i++) {
    auto groups = get_groups(i);
    D("* i=%d\n", i);
    auto edges = extra_edges(groups, 0, groups.size(), i);
    solve(groups, 0, groups.size(), edges, i);
  }
}
}  // namespace forest

vector<int> find_colors(int _n, int m, vector<int> a, vector<int> b) {
  n = _n;
  for (int i = 0; i < n; i++) {
    proposed_colors.push_back(ACTUAL_COLOR);
  }
  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);
  }
  forest::go();

  vector<int> ret;
  for (int i = 0; i < n; i++) {
    int g = forest::get(i);
    ret.push_back(g);
  }
  return ret;
}
}  // namespace collapse

namespace grouping {
int n;
int nCollapsed;
int groupOf[MAX_N];
vector<int> members[MAX_N];
vector<int> proposed_colors;

/*
 * 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) {
  DA(mask.size() == nCollapsed);

  for (int i = 0; i < n; i++) {
    proposed_colors[i] = mask[groupOf[i]];
  }
  return perform_experiment(proposed_colors);
}
}  // namespace grouping

// solution to subtask where graph is a coloring
namespace coloring {
int n;
vector<int> adjlist[MAX_N];
vector<int> proposed_colors;

int known_colors[MAX_N];

namespace divide {
int mark[MAX_N];

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

void go() {
  fill(mark, mark + n, -1);
  mark[0] = 0;
  dfs(0);
}
}  // namespace divide

namespace components {
int TT;
int seen[MAX_N];

// Mark all as seen from u.
void dfs(int u) {
  // D("++ got to %d\n", 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(v);
    }
  }
}

// Return number of components in a vector
int num_components(vector<int> &vertices) {
  TT++;
  int ret = 0;
  for (auto u : vertices) {
    if (seen[u] != TT) {
      // D("+ new component %d\n", u);
      ret++;
      dfs(u);
    }
  }
  return ret;
}
}  // namespace components

void print_vec(vector<int> &v) {
  D("[");
  for (auto i = 0; i < (int)v.size(); i++) {
    if (i > 0) {
      D(", ");
    }
    D("%d", v[i]);
  }
  D("]");
}

// 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) {
  D("find_of_color (color=%d, here=%d):\n", color, here);
  D(" subject: ");
  print_vec(subject);
  D("\n");
  D(" test: ");
  print_vec(test);
  D("\n");

  vector<int> ret;
  if (subject.size() <= 1) {
    for (auto u : subject) {
      known_colors[u] = color;
      ret.push_back(u);
      D("! identified %d as %d\n", u, color);
    }
    DA(!ret.empty());
    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() + components::num_components(test);
  auto actual = grouping::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) {
    // D("pushing %d [proposed_color=%d]\n", u, proposed_colors[u]);
    test.push_back(u);
    if (known_colors[u] == color) {
      // D("setting %d to %d\n", u, color);
      proposed_colors[u] = color;
    }
  }
  auto test_components = components::num_components(test);
  int if_none_right = right.size() + test_components;
  D("here=%d, if_none_right = %d test_components=%d, test=", here,
    if_none_right, test_components);
  print_vec(test);
  D(" left=");
  print_vec(left);
  D(" right=");
  print_vec(right);
  D(" ret=");
  print_vec(ret);
  D("\n");

  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();
  }

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

  if (actual < if_none) {
  // there's some on the left
  auto ret_right = find_of_color(color, right, test, actual);
  for (auto u: ret_right) {
  ret.push_back(u);
  }
  }

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

  DA(!ret.empty());
  return ret;
}

vector<int> find_colors(int _n, int m, vector<int> a, vector<int> b,
                        int num_colors) {
  n = _n;
  for (int i = 0; i < n; i++) {
    proposed_colors.push_back(ACTUAL_COLOR);
    known_colors[i] = -1;
  }
  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);
  }

  if (b.size() == 0) {
    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];

  divide::go();
  for (int i = 0; i < n; i++) {
    DA(divide::mark[i] == 0 || divide::mark[i] == 1);
    parts[divide::mark[i]].push_back(i);
  }

  for (int z = 0; z < 2; z++) {
    for (auto u : parts[z]) {
      proposed_colors[u] = 0;
    }
    comp[z] = components::num_components(parts[z]);
    D("comp[%d] = %d\n", z, comp[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 (int i = 0; i < n; i++) {
        DA(proposed_colors[i] == ACTUAL_COLOR);
      }

      for (auto u : parts[z ^ 1]) {
        proposed_colors[u] = c;
      }
      int if_none = parts[z].size() + comp[z ^ 1];
      auto init = grouping::queryGroups(proposed_colors);
      D("* trying color=%d, z=%d [if_none=%d, init=%d]\n", c, z, if_none, init);

      if (init < if_none) {
        D("* starting color=%d, z=%d [if_none=%d, init=%d]\n", c, z, if_none,
          init);
        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) {
  int m = a.size();
  // Returned solution has the property that every color component has a
  // distinct value. We use this for grouping.
  auto collapsed_colors = collapse::find_colors(n, m, a, b);

  grouping::n = n;
  for (int i = 0; i < n; i++) {
    grouping::proposed_colors.push_back(ACTUAL_COLOR);
  }

  grouping::nCollapsed = 0;
  unordered_map<int, int> remap;
  D("remapped:\n");
  for (int i = 0; i < n; i++) {
    auto c = collapsed_colors[i];
    if (remap.count(c) == 0) {
      remap[c] = grouping::nCollapsed;
      grouping::nCollapsed++;
    }
    grouping::groupOf[i] = remap[c];
    grouping::members[remap[c]].push_back(i);
    D("%d ", remap[c]);
  }
  D("\n");

  set<pii> edgesCollapsed;
  for (int u = 0; u < grouping::nCollapsed; u++) {
    for (auto uMember : grouping::members[u]) {
      for (auto vMember : collapse::adjlist[uMember]) {
        auto v = grouping::groupOf[vMember];
        if (u != v && edgesCollapsed.count(make_pair(u, v)) == 0 &&
            edgesCollapsed.count(make_pair(v, u)) == 0) {
          edgesCollapsed.insert(make_pair(u, v));
        }
      }
    }
  }

  int mCollapsed = edgesCollapsed.size();
  vector<int> aCollapsed;
  vector<int> bCollapsed;
  for (auto e : edgesCollapsed) {
    aCollapsed.push_back(e.first);
    bCollapsed.push_back(e.second);
    D("collapsed edge from %d to %d\n", e.first, e.second);
  }

  auto groupedColors = coloring::find_colors(grouping::nCollapsed, mCollapsed,
                                             aCollapsed, bCollapsed, n);
  /*D("grouped colors:\n");
  for (auto g: groupedColors) {
      D("%d ", g);
  }
  D("\n");*/

  vector<int> known_colors;
  for (int i = 0; i < n; i++) {
    known_colors.push_back(groupedColors[grouping::groupOf[i]]);
  }

  return known_colors;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
3.0 / 3.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 352 KB #experiments: 13
2 Correct 1 ms 352 KB #experiments: 2
3 Correct 0 ms 352 KB #experiments: 5
4 Correct 0 ms 344 KB #experiments: 5
5 Correct 0 ms 348 KB #experiments: 3
6 Correct 1 ms 352 KB #experiments: 74
7 Correct 2 ms 348 KB #experiments: 197
8 Correct 4 ms 472 KB #experiments: 264
9 Correct 2 ms 352 KB #experiments: 231
10 Correct 4 ms 348 KB #experiments: 308
11 Correct 3 ms 608 KB #experiments: 307
12 Correct 4 ms 352 KB #experiments: 366
13 Correct 4 ms 348 KB #experiments: 385
14 Correct 1 ms 344 KB #experiments: 64
15 Correct 3 ms 344 KB #experiments: 254
16 Correct 5 ms 348 KB #experiments: 268
17 Correct 6 ms 344 KB #experiments: 293
18 Correct 6 ms 516 KB #experiments: 333
19 Correct 4 ms 352 KB #experiments: 343
20 Correct 5 ms 344 KB #experiments: 366
21 Correct 8 ms 600 KB #experiments: 385
22 Correct 3 ms 344 KB #experiments: 297
23 Correct 4 ms 488 KB #experiments: 271
24 Correct 6 ms 344 KB #experiments: 316
25 Correct 5 ms 344 KB #experiments: 354
26 Correct 4 ms 344 KB #experiments: 273
27 Correct 3 ms 472 KB #experiments: 326
28 Correct 3 ms 344 KB #experiments: 368
29 Correct 5 ms 344 KB #experiments: 303
30 Correct 5 ms 344 KB #experiments: 353
31 Correct 5 ms 344 KB #experiments: 288
32 Correct 4 ms 344 KB #experiments: 348
33 Correct 2 ms 344 KB #experiments: 112
34 Correct 6 ms 344 KB #experiments: 385

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 352 KB #experiments: 2
2 Correct 0 ms 352 KB #experiments: 5
3 Correct 0 ms 344 KB #experiments: 5
4 Correct 0 ms 348 KB #experiments: 3
5 Correct 1 ms 352 KB #experiments: 74
6 Correct 2 ms 348 KB #experiments: 197
7 Correct 4 ms 472 KB #experiments: 264
8 Correct 2 ms 352 KB #experiments: 231
9 Correct 4 ms 348 KB #experiments: 308
10 Correct 3 ms 608 KB #experiments: 307
11 Correct 4 ms 352 KB #experiments: 366
12 Correct 4 ms 348 KB #experiments: 385
13 Correct 21 ms 344 KB #experiments: 851
14 Correct 24 ms 588 KB #experiments: 988
15 Correct 35 ms 500 KB #experiments: 1449
16 Correct 34 ms 344 KB #experiments: 1431
17 Correct 52 ms 600 KB #experiments: 1921
18 Correct 57 ms 496 KB #experiments: 2175
19 Correct 54 ms 600 KB #experiments: 2359
20 Correct 9 ms 600 KB #experiments: 383
21 Correct 48 ms 504 KB #experiments: 2493

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 352 KB #experiments: 2
2 Correct 0 ms 352 KB #experiments: 5
3 Correct 0 ms 344 KB #experiments: 5
4 Correct 0 ms 348 KB #experiments: 3
5 Correct 1 ms 344 KB #experiments: 64
6 Correct 3 ms 344 KB #experiments: 254
7 Correct 5 ms 348 KB #experiments: 268
8 Correct 6 ms 344 KB #experiments: 293
9 Correct 6 ms 516 KB #experiments: 333
10 Correct 4 ms 352 KB #experiments: 343
11 Correct 5 ms 344 KB #experiments: 366
12 Correct 8 ms 600 KB #experiments: 385
13 Correct 66 ms 1368 KB #experiments: 997
14 Correct 113 ms 1368 KB #experiments: 1401
15 Correct 115 ms 1368 KB #experiments: 1709
16 Correct 150 ms 1368 KB #experiments: 1923
17 Correct 159 ms 1620 KB #experiments: 2194
18 Correct 177 ms 1720 KB #experiments: 2304
19 Correct 217 ms 2224 KB #experiments: 2397
20 Correct 21 ms 1368 KB #experiments: 309
21 Correct 345 ms 3252 KB #experiments: 2493

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 352 KB #experiments: 13
2 Correct 1 ms 352 KB #experiments: 2
3 Correct 0 ms 352 KB #experiments: 5
4 Correct 0 ms 344 KB #experiments: 5
5 Correct 0 ms 348 KB #experiments: 3
6 Correct 1 ms 352 KB #experiments: 74
7 Correct 2 ms 348 KB #experiments: 197
8 Correct 4 ms 472 KB #experiments: 264
9 Correct 2 ms 352 KB #experiments: 231
10 Correct 4 ms 348 KB #experiments: 308
11 Correct 3 ms 608 KB #experiments: 307
12 Correct 4 ms 352 KB #experiments: 366
13 Correct 4 ms 348 KB #experiments: 385
14 Correct 1 ms 344 KB #experiments: 64
15 Correct 3 ms 344 KB #experiments: 254
16 Correct 5 ms 348 KB #experiments: 268
17 Correct 6 ms 344 KB #experiments: 293
18 Correct 6 ms 516 KB #experiments: 333
19 Correct 4 ms 352 KB #experiments: 343
20 Correct 5 ms 344 KB #experiments: 366
21 Correct 8 ms 600 KB #experiments: 385
22 Correct 3 ms 344 KB #experiments: 297
23 Correct 4 ms 488 KB #experiments: 271
24 Correct 6 ms 344 KB #experiments: 316
25 Correct 5 ms 344 KB #experiments: 354
26 Correct 4 ms 344 KB #experiments: 273
27 Correct 3 ms 472 KB #experiments: 326
28 Correct 3 ms 344 KB #experiments: 368
29 Correct 5 ms 344 KB #experiments: 303
30 Correct 5 ms 344 KB #experiments: 353
31 Correct 5 ms 344 KB #experiments: 288
32 Correct 4 ms 344 KB #experiments: 348
33 Correct 2 ms 344 KB #experiments: 112
34 Correct 6 ms 344 KB #experiments: 385
35 Correct 21 ms 344 KB #experiments: 851
36 Correct 24 ms 588 KB #experiments: 988
37 Correct 35 ms 500 KB #experiments: 1449
38 Correct 34 ms 344 KB #experiments: 1431
39 Correct 52 ms 600 KB #experiments: 1921
40 Correct 57 ms 496 KB #experiments: 2175
41 Correct 54 ms 600 KB #experiments: 2359
42 Correct 9 ms 600 KB #experiments: 383
43 Correct 48 ms 504 KB #experiments: 2493
44 Correct 66 ms 1368 KB #experiments: 997
45 Correct 113 ms 1368 KB #experiments: 1401
46 Correct 115 ms 1368 KB #experiments: 1709
47 Correct 150 ms 1368 KB #experiments: 1923
48 Correct 159 ms 1620 KB #experiments: 2194
49 Correct 177 ms 1720 KB #experiments: 2304
50 Correct 217 ms 2224 KB #experiments: 2397
51 Correct 21 ms 1368 KB #experiments: 309
52 Correct 345 ms 3252 KB #experiments: 2493
53 Correct 79 ms 528 KB #experiments: 2025
54 Correct 91 ms 592 KB #experiments: 2043
55 Correct 79 ms 600 KB #experiments: 2068
56 Correct 71 ms 600 KB #experiments: 2036
57 Correct 167 ms 1660 KB #experiments: 1636
58 Correct 207 ms 1640 KB #experiments: 2089
59 Correct 180 ms 1680 KB #experiments: 1873
60 Correct 282 ms 1768 KB #experiments: 2364
61 Correct 43 ms 508 KB #experiments: 1655
62 Correct 54 ms 496 KB #experiments: 2033
63 Correct 56 ms 760 KB #experiments: 2352
64 Correct 59 ms 580 KB #experiments: 1974
65 Correct 62 ms 588 KB #experiments: 1985
66 Correct 75 ms 600 KB #experiments: 2014
67 Correct 68 ms 600 KB #experiments: 2031
68 Correct 74 ms 600 KB #experiments: 1938
69 Correct 64 ms 608 KB #experiments: 2004
70 Correct 94 ms 600 KB #experiments: 2043
71 Correct 75 ms 600 KB #experiments: 1934
72 Correct 57 ms 596 KB #experiments: 1977
73 Correct 71 ms 552 KB #experiments: 1955
74 Correct 71 ms 564 KB #experiments: 2034
75 Correct 55 ms 600 KB #experiments: 1960
76 Correct 65 ms 600 KB #experiments: 2019
77 Correct 69 ms 600 KB #experiments: 1954
78 Correct 67 ms 620 KB #experiments: 2002
79 Correct 71 ms 600 KB #experiments: 1913
80 Correct 77 ms 632 KB #experiments: 1993
81 Correct 98 ms 652 KB #experiments: 1988
82 Correct 138 ms 936 KB #experiments: 2381
83 Correct 186 ms 1112 KB #experiments: 1819
84 Correct 278 ms 2116 KB #experiments: 2392
85 Correct 17 ms 600 KB #experiments: 470
86 Correct 243 ms 1356 KB #experiments: 2493