Submission #1099923

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1099923	2024-10-12T05:52:27 Z	model_code	Sphinx's Riddle (IOI24_sphinx)	C++17	50 / 100	173 ms	1204 KB

sphinx

// partially_correct/solution-partial.cpp

#include <algorithm>
#include <queue>

#include "sphinx.h"

using namespace std;

int count_components(int N, vector<vector<int>> &adj, 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 : adj[cur]) {
        if (!vis[nxt] && col[nxt] == col[cur]) {
          vis[nxt] = true;
          q.push(nxt);
        }
      }
    }
  }
  return cnt;
}

vector<int> find_components(int N, vector<vector<int>> &adj) {
  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, adj, 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, adj, 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);
  }

  vector<int> cid(N, -1);
  for (int c = 0; c < (int)comps.size(); ++c) {
    for (int v : comps[c]) cid[v] = c;
  }
  return cid;
}

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

  auto F = find_components(N, adj);

  return F;
}

Subtask #0

0.0 / 0.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	0 ms	344 KB	Partially correct

Subtask #1

1.5 / 3.0

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

Subtask #2

3.5 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	0 ms	344 KB	Partially correct
2	Correct	0 ms	344 KB	#experiments: 1
3	Correct	0 ms	344 KB	#experiments: 1
4	Partially correct	0 ms	344 KB	Partially correct
5	Partially correct	0 ms	344 KB	Partially correct
6	Partially correct	1 ms	344 KB	Partially correct
7	Partially correct	1 ms	344 KB	Partially correct
8	Partially correct	2 ms	344 KB	Partially correct
9	Partially correct	2 ms	344 KB	Partially correct
10	Partially correct	3 ms	344 KB	Partially correct
11	Partially correct	2 ms	344 KB	Partially correct
12	Partially correct	1 ms	344 KB	Partially correct
13	Partially correct	1 ms	344 KB	Partially correct
14	Partially correct	1 ms	344 KB	Partially correct
15	Partially correct	2 ms	344 KB	Partially correct
16	Partially correct	2 ms	344 KB	Partially correct
17	Partially correct	2 ms	596 KB	Partially correct
18	Partially correct	2 ms	344 KB	Partially correct
19	Partially correct	3 ms	344 KB	Partially correct
20	Partially correct	2 ms	344 KB	Partially correct
21	Partially correct	1 ms	344 KB	Partially correct
22	Partially correct	1 ms	344 KB	Partially correct
23	Partially correct	1 ms	344 KB	Partially correct
24	Partially correct	1 ms	344 KB	Partially correct
25	Partially correct	1 ms	344 KB	Partially correct
26	Partially correct	2 ms	344 KB	Partially correct
27	Partially correct	2 ms	344 KB	Partially correct
28	Partially correct	1 ms	344 KB	Partially correct
29	Partially correct	3 ms	344 KB	Partially correct
30	Partially correct	1 ms	344 KB	Partially correct
31	Partially correct	2 ms	344 KB	Partially correct
32	Partially correct	2 ms	344 KB	Partially correct
33	Partially correct	2 ms	344 KB	Partially correct
34	Partially correct	1 ms	344 KB	Partially correct

Subtask #3

16.5 / 33.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	#experiments: 1
2	Correct	0 ms	344 KB	#experiments: 1
3	Partially correct	0 ms	344 KB	Partially correct
4	Partially correct	0 ms	344 KB	Partially correct
5	Partially correct	1 ms	344 KB	Partially correct
6	Partially correct	1 ms	344 KB	Partially correct
7	Partially correct	2 ms	344 KB	Partially correct
8	Partially correct	2 ms	344 KB	Partially correct
9	Partially correct	3 ms	344 KB	Partially correct
10	Partially correct	2 ms	344 KB	Partially correct
11	Partially correct	1 ms	344 KB	Partially correct
12	Partially correct	1 ms	344 KB	Partially correct
13	Partially correct	10 ms	344 KB	Partially correct
14	Partially correct	13 ms	344 KB	Partially correct
15	Partially correct	24 ms	344 KB	Partially correct
16	Partially correct	18 ms	356 KB	Partially correct
17	Partially correct	25 ms	440 KB	Partially correct
18	Partially correct	33 ms	448 KB	Partially correct
19	Partially correct	20 ms	424 KB	Partially correct
20	Partially correct	5 ms	348 KB	Partially correct
21	Partially correct	5 ms	456 KB	Partially correct

Subtask #4

10.5 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	#experiments: 1
2	Correct	0 ms	344 KB	#experiments: 1
3	Partially correct	0 ms	344 KB	Partially correct
4	Partially correct	0 ms	344 KB	Partially correct
5	Partially correct	1 ms	344 KB	Partially correct
6	Partially correct	2 ms	344 KB	Partially correct
7	Partially correct	2 ms	344 KB	Partially correct
8	Partially correct	2 ms	596 KB	Partially correct
9	Partially correct	2 ms	344 KB	Partially correct
10	Partially correct	3 ms	344 KB	Partially correct
11	Partially correct	2 ms	344 KB	Partially correct
12	Partially correct	1 ms	344 KB	Partially correct
13	Partially correct	63 ms	1172 KB	Partially correct
14	Partially correct	105 ms	1180 KB	Partially correct
15	Partially correct	159 ms	1180 KB	Partially correct
16	Partially correct	146 ms	1112 KB	Partially correct
17	Partially correct	141 ms	1168 KB	Partially correct
18	Partially correct	124 ms	1168 KB	Partially correct
19	Partially correct	86 ms	1196 KB	Partially correct
20	Partially correct	35 ms	1172 KB	Partially correct
21	Partially correct	26 ms	1204 KB	Partially correct

Subtask #5

18.0 / 36.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	0 ms	344 KB	Partially correct
2	Correct	0 ms	344 KB	#experiments: 1
3	Correct	0 ms	344 KB	#experiments: 1
4	Partially correct	0 ms	344 KB	Partially correct
5	Partially correct	0 ms	344 KB	Partially correct
6	Partially correct	1 ms	344 KB	Partially correct
7	Partially correct	1 ms	344 KB	Partially correct
8	Partially correct	2 ms	344 KB	Partially correct
9	Partially correct	2 ms	344 KB	Partially correct
10	Partially correct	3 ms	344 KB	Partially correct
11	Partially correct	2 ms	344 KB	Partially correct
12	Partially correct	1 ms	344 KB	Partially correct
13	Partially correct	1 ms	344 KB	Partially correct
14	Partially correct	1 ms	344 KB	Partially correct
15	Partially correct	2 ms	344 KB	Partially correct
16	Partially correct	2 ms	344 KB	Partially correct
17	Partially correct	2 ms	596 KB	Partially correct
18	Partially correct	2 ms	344 KB	Partially correct
19	Partially correct	3 ms	344 KB	Partially correct
20	Partially correct	2 ms	344 KB	Partially correct
21	Partially correct	1 ms	344 KB	Partially correct
22	Partially correct	1 ms	344 KB	Partially correct
23	Partially correct	1 ms	344 KB	Partially correct
24	Partially correct	1 ms	344 KB	Partially correct
25	Partially correct	1 ms	344 KB	Partially correct
26	Partially correct	2 ms	344 KB	Partially correct
27	Partially correct	2 ms	344 KB	Partially correct
28	Partially correct	1 ms	344 KB	Partially correct
29	Partially correct	3 ms	344 KB	Partially correct
30	Partially correct	1 ms	344 KB	Partially correct
31	Partially correct	2 ms	344 KB	Partially correct
32	Partially correct	2 ms	344 KB	Partially correct
33	Partially correct	2 ms	344 KB	Partially correct
34	Partially correct	1 ms	344 KB	Partially correct
35	Partially correct	10 ms	344 KB	Partially correct
36	Partially correct	13 ms	344 KB	Partially correct
37	Partially correct	24 ms	344 KB	Partially correct
38	Partially correct	18 ms	356 KB	Partially correct
39	Partially correct	25 ms	440 KB	Partially correct
40	Partially correct	33 ms	448 KB	Partially correct
41	Partially correct	20 ms	424 KB	Partially correct
42	Partially correct	5 ms	348 KB	Partially correct
43	Partially correct	5 ms	456 KB	Partially correct
44	Partially correct	63 ms	1172 KB	Partially correct
45	Partially correct	105 ms	1180 KB	Partially correct
46	Partially correct	159 ms	1180 KB	Partially correct
47	Partially correct	146 ms	1112 KB	Partially correct
48	Partially correct	141 ms	1168 KB	Partially correct
49	Partially correct	124 ms	1168 KB	Partially correct
50	Partially correct	86 ms	1196 KB	Partially correct
51	Partially correct	35 ms	1172 KB	Partially correct
52	Partially correct	26 ms	1204 KB	Partially correct
53	Partially correct	30 ms	484 KB	Partially correct
54	Partially correct	40 ms	344 KB	Partially correct
55	Partially correct	41 ms	344 KB	Partially correct
56	Partially correct	51 ms	344 KB	Partially correct
57	Partially correct	20 ms	848 KB	Partially correct
58	Partially correct	18 ms	768 KB	Partially correct
59	Partially correct	19 ms	1000 KB	Partially correct
60	Partially correct	14 ms	780 KB	Partially correct
61	Partially correct	15 ms	456 KB	Partially correct
62	Partially correct	10 ms	704 KB	Partially correct
63	Partially correct	10 ms	344 KB	Partially correct
64	Partially correct	48 ms	524 KB	Partially correct
65	Partially correct	46 ms	520 KB	Partially correct
66	Partially correct	62 ms	344 KB	Partially correct
67	Partially correct	44 ms	344 KB	Partially correct
68	Partially correct	61 ms	596 KB	Partially correct
69	Partially correct	68 ms	344 KB	Partially correct
70	Partially correct	57 ms	544 KB	Partially correct
71	Partially correct	59 ms	344 KB	Partially correct
72	Partially correct	32 ms	484 KB	Partially correct
73	Partially correct	44 ms	492 KB	Partially correct
74	Partially correct	44 ms	516 KB	Partially correct
75	Partially correct	56 ms	344 KB	Partially correct
76	Partially correct	57 ms	536 KB	Partially correct
77	Partially correct	68 ms	344 KB	Partially correct
78	Partially correct	56 ms	344 KB	Partially correct
79	Partially correct	68 ms	344 KB	Partially correct
80	Partially correct	59 ms	344 KB	Partially correct
81	Partially correct	73 ms	352 KB	Partially correct
82	Partially correct	23 ms	612 KB	Partially correct
83	Partially correct	173 ms	936 KB	Partially correct
84	Partially correct	114 ms	1132 KB	Partially correct
85	Partially correct	18 ms	600 KB	Partially correct
86	Partially correct	15 ms	604 KB	Partially correct