oj.uz

Submission #1099896

# Submission time Handle Problem Language Result Execution time Memory
1099896 2024-10-12T05:47:05 Z model_code Sphinx's Riddle (IOI24_sphinx) C++17
100 / 100
 397 ms 4140 KB 
// correct/BM-full.cpp

#include <set>

#include "sphinx.h"

using namespace std;

int N;
int p[250];
vector<int> edge[250];
vector<int> ord;
bool reached[250];
set<int> unchecked;
bool keep[250];
set<int> ccEdge[250];
set<int> cc;
int parity[250];

int where(int x) {
  if (p[x] < 0) return x;
  return (p[x] = where(p[x]));
}

int color(int x) { return (ord[x] >= 0 ? ord[x] + N : where(x)); }

void dfs(int x) {
  reached[x] = true;
  for (int i : edge[x]) {
    if (!reached[i] && color(x) == color(i)) dfs(i);
  }
}

int expected() {
  for (int i = 0; i < N; i++) reached[i] = false;

  int sum = 0;
  for (int i = 0; i < N; i++) {
    if (!reached[i]) {
      sum++;
      dfs(i);
    }
  }

  return sum;
}

void pDfs(int x) {
  reached[x] = true;
  for (int i : ccEdge[x]) {
    if (!reached[i]) {
      parity[i] = 1 - parity[x];
      pDfs(i);
    }
  }
}

vector<int> find_colours(int NN, vector<int> X, vector<int> Y) {
  N = NN;
  ord.resize(N);
  for (int i = 0; i < N; i++) p[i] = -1;

  int M = X.size();
  for (int i = 0; i < M; i++) {
    edge[Y[i]].push_back(X[i]);
    edge[X[i]].push_back(Y[i]);
  }

  for (int i = 1; i < N; i++) {
    while (true) {
      for (int j = 0; j <= i; j++) ord[j] = -1;
      for (int j = i + 1; j < N; j++) ord[j] = N;
      if (perform_experiment(ord) == expected()) break;

      unchecked.clear();
      for (int j = 0; j < i; j++) {
        if (where(j) != i) unchecked.insert(where(j));
      }

      vector<int> vec(unchecked.size());
      int pos = 0;
      for (int j : unchecked) vec[pos++] = j;

      int a = 0, b = pos - 1;
      while (a != b) {
        int half = (a + b) / 2;
        for (int j = 0; j < N; j++) keep[j] = false;
        for (int j = a; j <= half; j++) keep[vec[j]] = true;
        for (int j = 0; j < i; j++) {
          if (keep[where(j)]) {
            ord[j] = -1;
          } else {
            ord[j] = N;
          }
        }
        ord[i] = -1;
        for (int j = i + 1; j < N; j++) ord[j] = N;

        if (perform_experiment(ord) == expected()) {
          a = half + 1;
        } else {
          b = half;
        }
      }
      p[where(vec[a])] = i;
    }
  }

  for (int i = 0; i < N; i++) cc.insert(where(i));
  vector<int> F(N);
  for (int i = 0; i < N; i++) F[i] = -1;
  if (cc.size() == 1) {
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) ord[j] = -1;
      ord[0] = i;
      if (perform_experiment(ord) == 1) {
        for (int j = 0; j < N; j++) F[j] = i;
        break;
      }
    }
  } else {
    for (int i = 0; i < N; i++) {
      for (int j : edge[i]) {
        if (where(i) != where(j)) {
          ccEdge[where(i)].insert(where(j));
          ccEdge[where(j)].insert(where(i));
        }
      }
    }

    for (int i = 0; i < N; i++) reached[i] = false;
    pDfs((*cc.begin()));

    for (int par = 0; par < 2; par++) {
      for (int i = 0; i < N; i++) {
        while (true) {
          for (int j = 0; j < N; j++) {
            if (parity[where(j)] == par || F[where(j)] != -1) {
              ord[j] = i;
            } else {
              ord[j] = -1;
            }
          }

          if (perform_experiment(ord) == expected()) break;

          unchecked.clear();
          for (int j = 0; j < N; j++) {
            if (parity[where(j)] == 1 - par && F[where(j)] == -1)
              unchecked.insert(where(j));
          }

          vector<int> vec(unchecked.size());
          int pos = 0;
          for (int j : unchecked) vec[pos++] = j;

          int a = 0, b = pos - 1;
          while (a != b) {
            int half = (a + b) / 2;
            for (int j = 0; j < N; j++) keep[j] = false;
            for (int j = a; j <= half; j++)
              if (F[vec[j]] == -1) keep[vec[j]] = true;

            for (int j = 0; j < N; j++) {
              if (keep[where(j)]) {
                ord[j] = -1;
              } else {
                ord[j] = i;
              }
            }

            if (perform_experiment(ord) == expected()) {
              a = half + 1;
            } else {
              b = half;
            }
          }
          F[where(vec[a])] = i;
        }
      }
    }

    for (int i = 0; i < N; i++) F[i] = F[where(i)];
  }

  return F;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
3.0 / 3.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB #experiments: 17
2 Correct 0 ms 344 KB #experiments: 3
3 Correct 0 ms 344 KB #experiments: 7
4 Correct 0 ms 344 KB #experiments: 7
5 Correct 0 ms 344 KB #experiments: 4
6 Correct 1 ms 344 KB #experiments: 123
7 Correct 2 ms 344 KB #experiments: 234
8 Correct 4 ms 344 KB #experiments: 282
9 Correct 2 ms 344 KB #experiments: 256
10 Correct 3 ms 344 KB #experiments: 314
11 Correct 4 ms 344 KB #experiments: 314
12 Correct 3 ms 344 KB #experiments: 369
13 Correct 3 ms 344 KB #experiments: 365
14 Correct 1 ms 344 KB #experiments: 113
15 Correct 5 ms 344 KB #experiments: 301
16 Correct 7 ms 344 KB #experiments: 314
17 Correct 8 ms 344 KB #experiments: 336
18 Correct 7 ms 372 KB #experiments: 361
19 Correct 8 ms 344 KB #experiments: 363
20 Correct 9 ms 344 KB #experiments: 379
21 Correct 7 ms 600 KB #experiments: 368
22 Correct 4 ms 344 KB #experiments: 359
23 Correct 6 ms 344 KB #experiments: 366
24 Correct 4 ms 344 KB #experiments: 353
25 Correct 4 ms 344 KB #experiments: 363
26 Correct 3 ms 344 KB #experiments: 381
27 Correct 3 ms 344 KB #experiments: 356
28 Correct 5 ms 344 KB #experiments: 370
29 Correct 4 ms 600 KB #experiments: 362
30 Correct 4 ms 344 KB #experiments: 361
31 Correct 5 ms 344 KB #experiments: 341
32 Correct 9 ms 344 KB #experiments: 368
33 Correct 3 ms 344 KB #experiments: 170
34 Correct 5 ms 344 KB #experiments: 373

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB #experiments: 3
2 Correct 0 ms 344 KB #experiments: 7
3 Correct 0 ms 344 KB #experiments: 7
4 Correct 0 ms 344 KB #experiments: 4
5 Correct 1 ms 344 KB #experiments: 123
6 Correct 2 ms 344 KB #experiments: 234
7 Correct 4 ms 344 KB #experiments: 282
8 Correct 2 ms 344 KB #experiments: 256
9 Correct 3 ms 344 KB #experiments: 314
10 Correct 4 ms 344 KB #experiments: 314
11 Correct 3 ms 344 KB #experiments: 369
12 Correct 3 ms 344 KB #experiments: 365
13 Correct 30 ms 452 KB #experiments: 1101
14 Correct 40 ms 448 KB #experiments: 1159
15 Correct 41 ms 344 KB #experiments: 1536
16 Correct 39 ms 344 KB #experiments: 1480
17 Correct 41 ms 472 KB #experiments: 1930
18 Correct 49 ms 480 KB #experiments: 2154
19 Correct 58 ms 600 KB #experiments: 2360
20 Correct 12 ms 472 KB #experiments: 632
21 Correct 66 ms 492 KB #experiments: 2402

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB #experiments: 3
2 Correct 0 ms 344 KB #experiments: 7
3 Correct 0 ms 344 KB #experiments: 7
4 Correct 0 ms 344 KB #experiments: 4
5 Correct 1 ms 344 KB #experiments: 113
6 Correct 5 ms 344 KB #experiments: 301
7 Correct 7 ms 344 KB #experiments: 314
8 Correct 8 ms 344 KB #experiments: 336
9 Correct 7 ms 372 KB #experiments: 361
10 Correct 8 ms 344 KB #experiments: 363
11 Correct 9 ms 344 KB #experiments: 379
12 Correct 7 ms 600 KB #experiments: 368
13 Correct 145 ms 1112 KB #experiments: 1247
14 Correct 187 ms 1196 KB #experiments: 1656
15 Correct 198 ms 1200 KB #experiments: 1945
16 Correct 254 ms 1360 KB #experiments: 2142
17 Correct 242 ms 1460 KB #experiments: 2355
18 Correct 291 ms 1720 KB #experiments: 2390
19 Correct 288 ms 2460 KB #experiments: 2432
20 Correct 57 ms 1112 KB #experiments: 558
21 Correct 271 ms 4140 KB #experiments: 2402

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB #experiments: 17
2 Correct 0 ms 344 KB #experiments: 3
3 Correct 0 ms 344 KB #experiments: 7
4 Correct 0 ms 344 KB #experiments: 7
5 Correct 0 ms 344 KB #experiments: 4
6 Correct 1 ms 344 KB #experiments: 123
7 Correct 2 ms 344 KB #experiments: 234
8 Correct 4 ms 344 KB #experiments: 282
9 Correct 2 ms 344 KB #experiments: 256
10 Correct 3 ms 344 KB #experiments: 314
11 Correct 4 ms 344 KB #experiments: 314
12 Correct 3 ms 344 KB #experiments: 369
13 Correct 3 ms 344 KB #experiments: 365
14 Correct 1 ms 344 KB #experiments: 113
15 Correct 5 ms 344 KB #experiments: 301
16 Correct 7 ms 344 KB #experiments: 314
17 Correct 8 ms 344 KB #experiments: 336
18 Correct 7 ms 372 KB #experiments: 361
19 Correct 8 ms 344 KB #experiments: 363
20 Correct 9 ms 344 KB #experiments: 379
21 Correct 7 ms 600 KB #experiments: 368
22 Correct 4 ms 344 KB #experiments: 359
23 Correct 6 ms 344 KB #experiments: 366
24 Correct 4 ms 344 KB #experiments: 353
25 Correct 4 ms 344 KB #experiments: 363
26 Correct 3 ms 344 KB #experiments: 381
27 Correct 3 ms 344 KB #experiments: 356
28 Correct 5 ms 344 KB #experiments: 370
29 Correct 4 ms 600 KB #experiments: 362
30 Correct 4 ms 344 KB #experiments: 361
31 Correct 5 ms 344 KB #experiments: 341
32 Correct 9 ms 344 KB #experiments: 368
33 Correct 3 ms 344 KB #experiments: 170
34 Correct 5 ms 344 KB #experiments: 373
35 Correct 30 ms 452 KB #experiments: 1101
36 Correct 40 ms 448 KB #experiments: 1159
37 Correct 41 ms 344 KB #experiments: 1536
38 Correct 39 ms 344 KB #experiments: 1480
39 Correct 41 ms 472 KB #experiments: 1930
40 Correct 49 ms 480 KB #experiments: 2154
41 Correct 58 ms 600 KB #experiments: 2360
42 Correct 12 ms 472 KB #experiments: 632
43 Correct 66 ms 492 KB #experiments: 2402
44 Correct 145 ms 1112 KB #experiments: 1247
45 Correct 187 ms 1196 KB #experiments: 1656
46 Correct 198 ms 1200 KB #experiments: 1945
47 Correct 254 ms 1360 KB #experiments: 2142
48 Correct 242 ms 1460 KB #experiments: 2355
49 Correct 291 ms 1720 KB #experiments: 2390
50 Correct 288 ms 2460 KB #experiments: 2432
51 Correct 57 ms 1112 KB #experiments: 558
52 Correct 271 ms 4140 KB #experiments: 2402
53 Correct 104 ms 824 KB #experiments: 2427
54 Correct 84 ms 536 KB #experiments: 2406
55 Correct 119 ms 552 KB #experiments: 2417
56 Correct 100 ms 580 KB #experiments: 2353
57 Correct 174 ms 1848 KB #experiments: 2410
58 Correct 129 ms 1880 KB #experiments: 2293
59 Correct 147 ms 1856 KB #experiments: 2300
60 Correct 179 ms 1980 KB #experiments: 2404
61 Correct 68 ms 488 KB #experiments: 2435
62 Correct 63 ms 492 KB #experiments: 2414
63 Correct 63 ms 516 KB #experiments: 2397
64 Correct 88 ms 536 KB #experiments: 2350
65 Correct 85 ms 528 KB #experiments: 2373
66 Correct 104 ms 548 KB #experiments: 2376
67 Correct 107 ms 552 KB #experiments: 2389
68 Correct 98 ms 564 KB #experiments: 2284
69 Correct 101 ms 564 KB #experiments: 2361
70 Correct 100 ms 556 KB #experiments: 2383
71 Correct 109 ms 344 KB #experiments: 2266
72 Correct 63 ms 512 KB #experiments: 2425
73 Correct 73 ms 500 KB #experiments: 2349
74 Correct 109 ms 776 KB #experiments: 2431
75 Correct 92 ms 544 KB #experiments: 2333
76 Correct 100 ms 600 KB #experiments: 2390
77 Correct 104 ms 556 KB #experiments: 2312
78 Correct 113 ms 600 KB #experiments: 2358
79 Correct 92 ms 600 KB #experiments: 2277
80 Correct 108 ms 600 KB #experiments: 2304
81 Correct 106 ms 600 KB #experiments: 2351
82 Correct 120 ms 1064 KB #experiments: 2405
83 Correct 296 ms 1064 KB #experiments: 2070
84 Correct 397 ms 2412 KB #experiments: 2399
85 Correct 39 ms 600 KB #experiments: 720
86 Correct 165 ms 1624 KB #experiments: 2404