oj.uz

Submission #1099892

# Submission time Handle Problem Language Result Execution time Memory
1099892 2024-10-12T05:46:18 Z model_code Sphinx's Riddle (IOI24_sphinx) C++17
100 / 100
 438 ms 1180 KB 
// model_solution/solution.cpp

#include <algorithm>
#include <queue>

#include "sphinx.h"

using namespace std;

int count_components(int N, vector<vector<int>> &e, vector<int> &col) {
  int cnt = 0;
  vector<bool> vis(N, false);
  queue<int> q;
  for (int i = 0; i < N; ++i) {
    if (vis[i]) {
      continue;
    }
    ++cnt;
    vis[i] = true;
    q.push(i);
    while (!q.empty()) {
      int cur = q.front();
      q.pop();
      for (int nxt : e[cur]) {
        if (!vis[nxt] && col[nxt] == col[cur]) {
          vis[nxt] = true;
          q.push(nxt);
        }
      }
    }
  }
  return cnt;
}

vector<vector<int>> find_components(int N, vector<vector<int>> &e) {
  vector<vector<int>> comps = {{0}};
  vector<int> ord(N);
  for (int u = 1; u < N; ++u) {
    ord.assign(N, N);
    int n = comps.size();
    vector<int> col(N, N);
    ord[u] = col[u] = -1;
    for (int i = 0; i < n; ++i) {
      for (int v : comps[i]) {
        ord[v] = -1;
        col[v] = i;
      }
    }
    int expected = count_components(N, e, col);
    int cnt = expected - perform_experiment(ord);
    if (cnt == 0) {
      comps.push_back({u});
      continue;
    }
    int lo = 0, hi = n;
    vector<int> comps_to_merge;
    while (cnt > 0) {
      while (lo + 1 < hi) {
        int mid = (lo + hi) / 2;
        ord.assign(N, N);
        col.assign(N, N);
        ord[u] = col[u] = -1;
        for (int i = mid; i < hi; ++i)
          for (int v : comps[i]) {
            ord[v] = -1;
            col[v] = i;
          }
        expected = count_components(N, e, col);
        if (perform_experiment(ord) < expected) {
          lo = mid;
        } else {
          hi = mid;
        }
      }
      comps_to_merge.push_back(lo);
      lo = 0, --hi;
      --cnt;
    }
    int to = comps_to_merge.back();
    comps_to_merge.pop_back();
    for (int from : comps_to_merge) {
      for (int v : comps[from]) {
        comps[to].push_back(v);
      }
      comps.erase(comps.begin() + from);
    }
    comps[to].push_back(u);
  }

  return comps;
}

void solve(vector<int> &A, vector<int> &FC, int N, vector<vector<int>> &e,
           vector<vector<int>> &comps) {
  vector<int> ord(N), col(N);
  for (int f = 0; f < N; ++f) {
    int lo = 0, hi = A.size();
    while (true) {
      ord.assign(N, f);
      col.assign(N, N);
      for (int i = lo; i < hi; ++i)
        for (int u : comps[A[i]]) {
          ord[u] = -1;
          col[u] = i;
        }
      int cnt = count_components(N, e, col) - perform_experiment(ord);
      if (cnt == 0) break;
      while (lo + 1 < hi) {
        int mid = (lo + hi) / 2;
        ord.assign(N, f);
        col.assign(N, N);
        for (int i = mid; i < hi; ++i)
          for (int u : comps[A[i]]) {
            ord[u] = -1;
            col[u] = i;
          }
        if (perform_experiment(ord) < count_components(N, e, col)) {
          lo = mid;
        } else {
          hi = mid;
        }
      }
      FC[A[lo]] = f;
      lo = 0, --hi;
      if (cnt == 1) break;
    }
  }
}

vector<int> find_colours(int N, vector<int> X, vector<int> Y) {
  vector<vector<int>> e(N);
  int M = X.size();
  for (int i = 0; i < M; ++i) {
    e[X[i]].push_back(Y[i]);
    e[Y[i]].push_back(X[i]);
  }

  auto comps = find_components(N, e);
  int n = comps.size();
  if (n == 1) {
    for (int f = 0; f < N; ++f) {
      vector<int> ord(N, f);
      ord[0] = -1;
      if (perform_experiment(ord) == 1) return vector<int>(N, f);
    }
  }

  vector<int> cid(N, -1);
  for (int c = 0; c < n; ++c)
    for (int u : comps[c]) cid[u] = c;
  vector<vector<int>> adj(n, vector<int>(n, 0));
  for (int i = 0; i < M; ++i) {
    int u = cid[X[i]], v = cid[Y[i]];
    if (u == v) continue;
    adj[u][v] = adj[v][u] = 1;
  }

  vector<int> vis(n, 0);
  queue<int> q;
  for (int i = 0; i < n; ++i) {
    if (vis[i]) continue;
    q.push(i);
    vis[i] = 1;
    while (!q.empty()) {
      int cur = q.front();
      q.pop();
      for (int nxt = 0; nxt < n; ++nxt) {
        if (adj[cur][nxt] && vis[nxt] == 0) {
          vis[nxt] = (vis[cur] == 1 ? 2 : 1);
          q.push(nxt);
        }
      }
    }
  }
  vector<int> A, B;
  for (int i = 0; i < n; ++i) {
    if (vis[i] == 1)
      A.push_back(i);
    else
      B.push_back(i);
  }

  vector<int> FC(n, -1);
  solve(A, FC, N, e, comps);
  solve(B, FC, N, e, comps);

  vector<int> F(N);
  for (int i = 0; i < N; ++i) F[i] = FC[cid[i]];
  return F;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
3.0 / 3.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB #experiments: 15
2 Correct 0 ms 344 KB #experiments: 2
3 Correct 0 ms 344 KB #experiments: 5
4 Correct 0 ms 344 KB #experiments: 5
5 Correct 0 ms 344 KB #experiments: 3
6 Correct 1 ms 344 KB #experiments: 74
7 Correct 3 ms 344 KB #experiments: 198
8 Correct 3 ms 344 KB #experiments: 267
9 Correct 3 ms 356 KB #experiments: 237
10 Correct 3 ms 612 KB #experiments: 316
11 Correct 3 ms 356 KB #experiments: 321
12 Correct 4 ms 352 KB #experiments: 427
13 Correct 3 ms 356 KB #experiments: 433
14 Correct 1 ms 356 KB #experiments: 64
15 Correct 3 ms 356 KB #experiments: 255
16 Correct 5 ms 356 KB #experiments: 271
17 Correct 3 ms 356 KB #experiments: 298
18 Correct 4 ms 356 KB #experiments: 346
19 Correct 6 ms 356 KB #experiments: 361
20 Correct 8 ms 612 KB #experiments: 393
21 Correct 5 ms 356 KB #experiments: 428
22 Correct 4 ms 456 KB #experiments: 383
23 Correct 4 ms 356 KB #experiments: 390
24 Correct 4 ms 356 KB #experiments: 379
25 Correct 5 ms 512 KB #experiments: 404
26 Correct 3 ms 356 KB #experiments: 375
27 Correct 5 ms 356 KB #experiments: 384
28 Correct 5 ms 356 KB #experiments: 404
29 Correct 4 ms 356 KB #experiments: 340
30 Correct 5 ms 356 KB #experiments: 380
31 Correct 6 ms 356 KB #experiments: 299
32 Correct 5 ms 356 KB #experiments: 377
33 Correct 1 ms 356 KB #experiments: 117
34 Correct 5 ms 356 KB #experiments: 416

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB #experiments: 2
2 Correct 0 ms 344 KB #experiments: 5
3 Correct 0 ms 344 KB #experiments: 5
4 Correct 0 ms 344 KB #experiments: 3
5 Correct 1 ms 344 KB #experiments: 74
6 Correct 3 ms 344 KB #experiments: 198
7 Correct 3 ms 344 KB #experiments: 267
8 Correct 3 ms 356 KB #experiments: 237
9 Correct 3 ms 612 KB #experiments: 316
10 Correct 3 ms 356 KB #experiments: 321
11 Correct 4 ms 352 KB #experiments: 427
12 Correct 3 ms 356 KB #experiments: 433
13 Correct 22 ms 356 KB #experiments: 851
14 Correct 35 ms 356 KB #experiments: 990
15 Correct 32 ms 440 KB #experiments: 1457
16 Correct 47 ms 444 KB #experiments: 1444
17 Correct 49 ms 612 KB #experiments: 1969
18 Correct 50 ms 356 KB #experiments: 2282
19 Correct 94 ms 448 KB #experiments: 2614
20 Correct 7 ms 344 KB #experiments: 383
21 Correct 96 ms 600 KB #experiments: 2741

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB #experiments: 2
2 Correct 0 ms 344 KB #experiments: 5
3 Correct 0 ms 344 KB #experiments: 5
4 Correct 0 ms 344 KB #experiments: 3
5 Correct 1 ms 356 KB #experiments: 64
6 Correct 3 ms 356 KB #experiments: 255
7 Correct 5 ms 356 KB #experiments: 271
8 Correct 3 ms 356 KB #experiments: 298
9 Correct 4 ms 356 KB #experiments: 346
10 Correct 6 ms 356 KB #experiments: 361
11 Correct 8 ms 612 KB #experiments: 393
12 Correct 5 ms 356 KB #experiments: 428
13 Correct 108 ms 1112 KB #experiments: 997
14 Correct 166 ms 1164 KB #experiments: 1403
15 Correct 205 ms 1112 KB #experiments: 1719
16 Correct 262 ms 1172 KB #experiments: 1947
17 Correct 224 ms 1176 KB #experiments: 2262
18 Correct 277 ms 1172 KB #experiments: 2420
19 Correct 316 ms 1176 KB #experiments: 2551
20 Correct 29 ms 1112 KB #experiments: 309
21 Correct 426 ms 1180 KB #experiments: 2734

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB #experiments: 15
2 Correct 0 ms 344 KB #experiments: 2
3 Correct 0 ms 344 KB #experiments: 5
4 Correct 0 ms 344 KB #experiments: 5
5 Correct 0 ms 344 KB #experiments: 3
6 Correct 1 ms 344 KB #experiments: 74
7 Correct 3 ms 344 KB #experiments: 198
8 Correct 3 ms 344 KB #experiments: 267
9 Correct 3 ms 356 KB #experiments: 237
10 Correct 3 ms 612 KB #experiments: 316
11 Correct 3 ms 356 KB #experiments: 321
12 Correct 4 ms 352 KB #experiments: 427
13 Correct 3 ms 356 KB #experiments: 433
14 Correct 1 ms 356 KB #experiments: 64
15 Correct 3 ms 356 KB #experiments: 255
16 Correct 5 ms 356 KB #experiments: 271
17 Correct 3 ms 356 KB #experiments: 298
18 Correct 4 ms 356 KB #experiments: 346
19 Correct 6 ms 356 KB #experiments: 361
20 Correct 8 ms 612 KB #experiments: 393
21 Correct 5 ms 356 KB #experiments: 428
22 Correct 4 ms 456 KB #experiments: 383
23 Correct 4 ms 356 KB #experiments: 390
24 Correct 4 ms 356 KB #experiments: 379
25 Correct 5 ms 512 KB #experiments: 404
26 Correct 3 ms 356 KB #experiments: 375
27 Correct 5 ms 356 KB #experiments: 384
28 Correct 5 ms 356 KB #experiments: 404
29 Correct 4 ms 356 KB #experiments: 340
30 Correct 5 ms 356 KB #experiments: 380
31 Correct 6 ms 356 KB #experiments: 299
32 Correct 5 ms 356 KB #experiments: 377
33 Correct 1 ms 356 KB #experiments: 117
34 Correct 5 ms 356 KB #experiments: 416
35 Correct 22 ms 356 KB #experiments: 851
36 Correct 35 ms 356 KB #experiments: 990
37 Correct 32 ms 440 KB #experiments: 1457
38 Correct 47 ms 444 KB #experiments: 1444
39 Correct 49 ms 612 KB #experiments: 1969
40 Correct 50 ms 356 KB #experiments: 2282
41 Correct 94 ms 448 KB #experiments: 2614
42 Correct 7 ms 344 KB #experiments: 383
43 Correct 96 ms 600 KB #experiments: 2741
44 Correct 108 ms 1112 KB #experiments: 997
45 Correct 166 ms 1164 KB #experiments: 1403
46 Correct 205 ms 1112 KB #experiments: 1719
47 Correct 262 ms 1172 KB #experiments: 1947
48 Correct 224 ms 1176 KB #experiments: 2262
49 Correct 277 ms 1172 KB #experiments: 2420
50 Correct 316 ms 1176 KB #experiments: 2551
51 Correct 29 ms 1112 KB #experiments: 309
52 Correct 426 ms 1180 KB #experiments: 2734
53 Correct 71 ms 492 KB #experiments: 2365
54 Correct 87 ms 512 KB #experiments: 2327
55 Correct 97 ms 524 KB #experiments: 2290
56 Correct 76 ms 532 KB #experiments: 2183
57 Correct 188 ms 860 KB #experiments: 2491
58 Correct 185 ms 848 KB #experiments: 2428
59 Correct 218 ms 772 KB #experiments: 2416
60 Correct 220 ms 784 KB #experiments: 2588
61 Correct 67 ms 604 KB #experiments: 2429
62 Correct 88 ms 596 KB #experiments: 2535
63 Correct 81 ms 600 KB #experiments: 2590
64 Correct 91 ms 504 KB #experiments: 2177
65 Correct 80 ms 520 KB #experiments: 2174
66 Correct 87 ms 512 KB #experiments: 2229
67 Correct 93 ms 516 KB #experiments: 2247
68 Correct 78 ms 344 KB #experiments: 2079
69 Correct 89 ms 344 KB #experiments: 2149
70 Correct 89 ms 528 KB #experiments: 2242
71 Correct 84 ms 344 KB #experiments: 2031
72 Correct 86 ms 464 KB #experiments: 2427
73 Correct 74 ms 496 KB #experiments: 2197
74 Correct 80 ms 752 KB #experiments: 2348
75 Correct 71 ms 344 KB #experiments: 2091
76 Correct 90 ms 520 KB #experiments: 2248
77 Correct 74 ms 344 KB #experiments: 2073
78 Correct 88 ms 344 KB #experiments: 2159
79 Correct 88 ms 344 KB #experiments: 2016
80 Correct 95 ms 344 KB #experiments: 2098
81 Correct 93 ms 344 KB #experiments: 2137
82 Correct 119 ms 600 KB #experiments: 2597
83 Correct 265 ms 1024 KB #experiments: 1853
84 Correct 438 ms 1112 KB #experiments: 2690
85 Correct 16 ms 600 KB #experiments: 471
86 Correct 225 ms 736 KB #experiments: 2615