oj.uz

Submission #1099914

# Submission time Handle Problem Language Result Execution time Memory
1099914 2024-10-12T05:50:37 Z model_code Sphinx's Riddle (IOI24_sphinx) C++17
43 / 100
 377 ms 1436 KB 
// failed/solution-unopt.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;
        }
      if (count_components(N, e, col) == perform_experiment(ord)) 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;
    }
  }
}

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: 16

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: 7
3 Correct 0 ms 344 KB #experiments: 7
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: 16
2 Correct 0 ms 344 KB #experiments: 2
3 Correct 0 ms 344 KB #experiments: 7
4 Correct 0 ms 344 KB #experiments: 7
5 Correct 0 ms 344 KB #experiments: 3
6 Correct 1 ms 344 KB #experiments: 74
7 Correct 2 ms 344 KB #experiments: 200
8 Correct 2 ms 428 KB #experiments: 269
9 Correct 2 ms 348 KB #experiments: 238
10 Correct 4 ms 352 KB #experiments: 318
11 Correct 4 ms 348 KB #experiments: 323
12 Correct 5 ms 344 KB #experiments: 428
13 Correct 6 ms 600 KB #experiments: 435
14 Correct 1 ms 344 KB #experiments: 64
15 Correct 5 ms 344 KB #experiments: 260
16 Correct 4 ms 344 KB #experiments: 278
17 Correct 4 ms 344 KB #experiments: 308
18 Correct 5 ms 352 KB #experiments: 365
19 Correct 8 ms 612 KB #experiments: 385
20 Correct 8 ms 468 KB #experiments: 427
21 Correct 9 ms 344 KB #experiments: 478
22 Correct 6 ms 344 KB #experiments: 396
23 Correct 4 ms 604 KB #experiments: 399
24 Correct 4 ms 344 KB #experiments: 393
25 Correct 7 ms 344 KB #experiments: 429
26 Correct 3 ms 344 KB #experiments: 379
27 Correct 5 ms 344 KB #experiments: 397
28 Correct 5 ms 600 KB #experiments: 426
29 Correct 5 ms 344 KB #experiments: 346
30 Correct 6 ms 456 KB #experiments: 403
31 Correct 5 ms 352 KB #experiments: 308
32 Correct 8 ms 608 KB #experiments: 404
33 Correct 2 ms 352 KB #experiments: 117
34 Correct 6 ms 348 KB #experiments: 435

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: 7
3 Correct 0 ms 344 KB #experiments: 7
4 Correct 0 ms 344 KB #experiments: 3
5 Correct 1 ms 344 KB #experiments: 74
6 Correct 2 ms 344 KB #experiments: 200
7 Correct 2 ms 428 KB #experiments: 269
8 Correct 2 ms 348 KB #experiments: 238
9 Correct 4 ms 352 KB #experiments: 318
10 Correct 4 ms 348 KB #experiments: 323
11 Correct 5 ms 344 KB #experiments: 428
12 Correct 6 ms 600 KB #experiments: 435
13 Correct 23 ms 356 KB #experiments: 853
14 Correct 22 ms 356 KB #experiments: 992
15 Correct 31 ms 452 KB #experiments: 1459
16 Correct 27 ms 420 KB #experiments: 1446
17 Correct 50 ms 440 KB #experiments: 1971
18 Correct 69 ms 452 KB #experiments: 2284
19 Correct 54 ms 452 KB #experiments: 2615
20 Correct 7 ms 344 KB #experiments: 383
21 Correct 57 ms 712 KB #experiments: 2743

Subtask #4
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB #experiments: 2
2 Correct 0 ms 344 KB #experiments: 7
3 Correct 0 ms 344 KB #experiments: 7
4 Correct 0 ms 344 KB #experiments: 3
5 Correct 1 ms 344 KB #experiments: 64
6 Correct 5 ms 344 KB #experiments: 260
7 Correct 4 ms 344 KB #experiments: 278
8 Correct 4 ms 344 KB #experiments: 308
9 Correct 5 ms 352 KB #experiments: 365
10 Correct 8 ms 612 KB #experiments: 385
11 Correct 8 ms 468 KB #experiments: 427
12 Correct 9 ms 344 KB #experiments: 478
13 Correct 127 ms 1112 KB #experiments: 999
14 Correct 153 ms 1112 KB #experiments: 1409
15 Correct 190 ms 1112 KB #experiments: 1734
16 Correct 224 ms 1168 KB #experiments: 1977
17 Correct 292 ms 1168 KB #experiments: 2338
18 Correct 355 ms 1172 KB #experiments: 2544
19 Correct 348 ms 1188 KB #experiments: 2714
20 Correct 31 ms 1112 KB #experiments: 309
21 Incorrect 377 ms 1436 KB #experiments reached 2751
22 Halted 0 ms 0 KB -

Subtask #5
0.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB #experiments: 16
2 Correct 0 ms 344 KB #experiments: 2
3 Correct 0 ms 344 KB #experiments: 7
4 Correct 0 ms 344 KB #experiments: 7
5 Correct 0 ms 344 KB #experiments: 3
6 Correct 1 ms 344 KB #experiments: 74
7 Correct 2 ms 344 KB #experiments: 200
8 Correct 2 ms 428 KB #experiments: 269
9 Correct 2 ms 348 KB #experiments: 238
10 Correct 4 ms 352 KB #experiments: 318
11 Correct 4 ms 348 KB #experiments: 323
12 Correct 5 ms 344 KB #experiments: 428
13 Correct 6 ms 600 KB #experiments: 435
14 Correct 1 ms 344 KB #experiments: 64
15 Correct 5 ms 344 KB #experiments: 260
16 Correct 4 ms 344 KB #experiments: 278
17 Correct 4 ms 344 KB #experiments: 308
18 Correct 5 ms 352 KB #experiments: 365
19 Correct 8 ms 612 KB #experiments: 385
20 Correct 8 ms 468 KB #experiments: 427
21 Correct 9 ms 344 KB #experiments: 478
22 Correct 6 ms 344 KB #experiments: 396
23 Correct 4 ms 604 KB #experiments: 399
24 Correct 4 ms 344 KB #experiments: 393
25 Correct 7 ms 344 KB #experiments: 429
26 Correct 3 ms 344 KB #experiments: 379
27 Correct 5 ms 344 KB #experiments: 397
28 Correct 5 ms 600 KB #experiments: 426
29 Correct 5 ms 344 KB #experiments: 346
30 Correct 6 ms 456 KB #experiments: 403
31 Correct 5 ms 352 KB #experiments: 308
32 Correct 8 ms 608 KB #experiments: 404
33 Correct 2 ms 352 KB #experiments: 117
34 Correct 6 ms 348 KB #experiments: 435
35 Correct 23 ms 356 KB #experiments: 853
36 Correct 22 ms 356 KB #experiments: 992
37 Correct 31 ms 452 KB #experiments: 1459
38 Correct 27 ms 420 KB #experiments: 1446
39 Correct 50 ms 440 KB #experiments: 1971
40 Correct 69 ms 452 KB #experiments: 2284
41 Correct 54 ms 452 KB #experiments: 2615
42 Correct 7 ms 344 KB #experiments: 383
43 Correct 57 ms 712 KB #experiments: 2743
44 Correct 127 ms 1112 KB #experiments: 999
45 Correct 153 ms 1112 KB #experiments: 1409
46 Correct 190 ms 1112 KB #experiments: 1734
47 Correct 224 ms 1168 KB #experiments: 1977
48 Correct 292 ms 1168 KB #experiments: 2338
49 Correct 355 ms 1172 KB #experiments: 2544
50 Correct 348 ms 1188 KB #experiments: 2714
51 Correct 31 ms 1112 KB #experiments: 309
52 Incorrect 377 ms 1436 KB #experiments reached 2751
53 Halted 0 ms 0 KB -