Submission #1099922

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1099922	2024-10-12T05:52:13 Z	model_code	Sphinx's Riddle (IOI24_sphinx)	C++17	21.5 / 100	233 ms	1176 KB

sphinx

// partially_correct/BM-partial-edge-check.cpp

#include <random>

#include "sphinx.h"

using namespace std;

int p[250];
bool checked[250];
vector<int> edge[250];
vector<int> ord;
bool reached[250];

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

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

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

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

  return sum;
}

vector<int> find_colours(int N, vector<int> X, vector<int> Y) {
  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++) {
    for (int j = 0; j < N; j++) checked[j] = false;

    for (int j : edge[i]) {
      if (j > i) continue;

      int pp = where(j);
      if (pp == i || checked[pp]) continue;

      for (int k = 0; k < N; k++) ord[k] = N;
      ord[i] = -1;
      ord[j] = -1;

      if (perform_experiment(ord) == expected(N)) {
        checked[pp] = true;
      } else {
        p[pp] = i;
      }
    }
  }

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

Subtask #0
0.0 / 0.0

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

Subtask #1
1.5 / 3.0

#	Verdict	Memory	Grader output
1	Partially correct	356 KB	Partially correct
2	Correct	352 KB	#experiments: 1
3	Partially correct	352 KB	Partially correct
4	Correct	344 KB	#experiments: 1

Subtask #2
3.5 / 7.0

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

Subtask #3
16.5 / 33.0

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

Subtask #4
0.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	0 ms	356 KB	Partially correct
2	Correct	0 ms	352 KB	#experiments: 1
3	Partially correct	0 ms	352 KB	Partially correct
4	Correct	0 ms	344 KB	#experiments: 1
5	Partially correct	1 ms	344 KB	Partially correct
6	Partially correct	2 ms	344 KB	Partially correct
7	Partially correct	4 ms	344 KB	Partially correct
8	Partially correct	6 ms	344 KB	Partially correct
9	Partially correct	7 ms	344 KB	Partially correct
10	Partially correct	8 ms	344 KB	Partially correct
11	Partially correct	16 ms	344 KB	Partially correct
12	Partially correct	15 ms	344 KB	Partially correct
13	Partially correct	51 ms	1112 KB	Partially correct
14	Partially correct	120 ms	1112 KB	Partially correct
15	Incorrect	233 ms	1176 KB	#experiments reached 2751
16	Halted	0 ms	0 KB	-

Subtask #5
0.0 / 36.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	0 ms	352 KB	Partially correct
2	Partially correct	0 ms	356 KB	Partially correct
3	Correct	0 ms	352 KB	#experiments: 1
4	Partially correct	0 ms	352 KB	Partially correct
5	Correct	0 ms	344 KB	#experiments: 1
6	Partially correct	1 ms	344 KB	Partially correct
7	Partially correct	1 ms	348 KB	Partially correct
8	Partially correct	1 ms	352 KB	Partially correct
9	Partially correct	1 ms	348 KB	Partially correct
10	Partially correct	1 ms	352 KB	Partially correct
11	Partially correct	1 ms	424 KB	Partially correct
12	Partially correct	1 ms	348 KB	Partially correct
13	Partially correct	1 ms	400 KB	Partially correct
14	Partially correct	1 ms	344 KB	Partially correct
15	Partially correct	2 ms	344 KB	Partially correct
16	Partially correct	4 ms	344 KB	Partially correct
17	Partially correct	6 ms	344 KB	Partially correct
18	Partially correct	7 ms	344 KB	Partially correct
19	Partially correct	8 ms	344 KB	Partially correct
20	Partially correct	16 ms	344 KB	Partially correct
21	Partially correct	15 ms	344 KB	Partially correct
22	Partially correct	5 ms	344 KB	Partially correct
23	Partially correct	5 ms	344 KB	Partially correct
24	Partially correct	4 ms	344 KB	Partially correct
25	Partially correct	7 ms	344 KB	Partially correct
26	Partially correct	1 ms	344 KB	Partially correct
27	Partially correct	0 ms	344 KB	Partially correct
28	Partially correct	1 ms	344 KB	Partially correct
29	Partially correct	2 ms	344 KB	Partially correct
30	Partially correct	6 ms	344 KB	Partially correct
31	Partially correct	4 ms	344 KB	Partially correct
32	Partially correct	12 ms	344 KB	Partially correct
33	Partially correct	1 ms	344 KB	Partially correct
34	Partially correct	14 ms	344 KB	Partially correct
35	Partially correct	9 ms	344 KB	Partially correct
36	Partially correct	6 ms	344 KB	Partially correct
37	Partially correct	9 ms	344 KB	Partially correct
38	Partially correct	10 ms	344 KB	Partially correct
39	Partially correct	9 ms	344 KB	Partially correct
40	Partially correct	8 ms	344 KB	Partially correct
41	Partially correct	6 ms	344 KB	Partially correct
42	Partially correct	5 ms	344 KB	Partially correct
43	Partially correct	5 ms	344 KB	Partially correct
44	Partially correct	51 ms	1112 KB	Partially correct
45	Partially correct	120 ms	1112 KB	Partially correct
46	Incorrect	233 ms	1176 KB	#experiments reached 2751
47	Halted	0 ms	0 KB	-

Submission #1099922

Compilation message

Subtask #0 0.0 / 0.0

Subtask #1 1.5 / 3.0

Subtask #2 3.5 / 7.0

Subtask #3 16.5 / 33.0

Subtask #4 0.0 / 21.0

Subtask #5 0.0 / 36.0

Subtask #0
0.0 / 0.0

Subtask #1
1.5 / 3.0

Subtask #2
3.5 / 7.0

Subtask #3
16.5 / 33.0

Subtask #4
0.0 / 21.0

Subtask #5
0.0 / 36.0