QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#553128	#9241. Sphinx	thomaswmy^#	28.5	168ms	4872kb	C++17	1.6kb	2024-09-08 09:22:34	2024-09-08 09:22:34

Judging History

你现在查看的是最新测评结果

[2024-09-08 09:22:34]
评测

测评结果：28.5
用时：168ms
内存：4872kb

查看

[2024-09-08 09:22:34]
提交

answer

#include <bits/stdc++.h>
#include "sphinx.h"
using namespace std;
const int NN=260;

int n;
vector<int> g[NN];
int tot;
bool vis[NN];

void dfs(int u,int n,vector<int> &col) {
  vis[u]=1;
  for(int v:g[u]) {
    if(vis[v]) continue;
    if(col[u]!=col[v]) continue;
    dfs(v,n,col);
  }
}

int calc(vector<int> &col,int n) {
  for(int i=0;i<n;i++) vis[i]=0;
  int res=0;
  for(int i=0;i<n;i++) {
    if(vis[i]) continue;
    dfs(i,n,col);
    res++;
  }
  return res;
}

void solve(int u,vector<int> &arr,vector<int> &col,int L,int R) {
  if(L>R) return ;
  vector<int> a,b;
  a.resize(n,n);
  b.resize(n,n);
  a[u]=col[u];
  b[u]=-1;
  if(L==R) {
    for(int i=L;i<=R;i++) a[arr[i]]=col[arr[i]],b[arr[i]]=-1;
    int val1=calc(a,n),val2=perform_experiment(b);
    if(val1!=val2) col[u]=col[arr[L]];
    return ;
  }
  int mid=L+R>>1;
  for(int i=L;i<=mid;i++) a[arr[i]]=col[arr[i]],b[arr[i]]=-1;
  int val1=calc(a,n),val2=perform_experiment(b);
  if(val1!=val2) solve(u,arr,col,L,mid);
  else solve(u,arr,col,mid+1,R);
}

vector<int> find_colours(int N,vector<int> X,vector<int> Y) {
    n=N;
    vector<int> col;
    col.resize(n);
    int m=X.size();
    for(int i=0;i<m;i++) {
      if(X[i]>Y[i]) swap(X[i],Y[i]);
      g[X[i]].push_back(Y[i]),g[Y[i]].push_back(X[i]);
    }
    tot=0;
    for(int i=1;i<n;i++) {
      vector<int> arr;
      col[i]=++tot;
      sort(g[i].begin(),g[i].end());
      for(int j:g[i]) {
        if(j<i) arr.push_back(j);
      }
      solve(i,arr,col,0,arr.size()-1);
    }
    return col;
}

源文件, 语言: C++17

詳細信息

Subtask #1:

score: 1.5

Acceptable Answer

Test #1:

score: 3

Accepted

time: 0ms

memory: 3804kb

input:

output:

result:

ok #experiments: 1

Test #2:

score: 3

Accepted

time: 1ms

memory: 4064kb

input:

output:

result:

ok #experiments: 1

Test #3:

score: 1.5

Acceptable Answer

time: 0ms

memory: 3788kb

input:

output:

result:

points 0.50 points  0.5

Test #4:

score: 1.5

Acceptable Answer

time: 1ms

memory: 3808kb

input:

output:

result:

points 0.50 points  0.5

Subtask #2:

score: 0

Wrong Answer

Dependency #1:

50%

Acceptable Answer

Test #5:

score: 3.5

Acceptable Answer

time: 0ms

memory: 3784kb

input:

1978433568
50
49
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
10
10
11
11
12
12
13
13
14
14
15
15
16
16
17
17
18
18
19
19
20
20
21
21
22
22
23
23
24
24
25
25
26
26
27
27
28
28
29
29
30
30
31
31
32
32
33
33
34
34
35
35
36
36
37
37
38
38
39
39
40
40
41
41
42
42
43
43
44
44
45
45
46
46
47
47
48
48
49
19784335...

output:

result:

points 0.50 points  0.5

Test #6:

score: 3.5

Acceptable Answer

time: 1ms

memory: 3784kb

input:

output:

result:

points 0.50 points  0.5

Test #7:

score: 3.5

Acceptable Answer

time: 0ms

memory: 4036kb

input:

1978433568
50
49
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
10
10
11
11
12
12
13
13
14
14
15
15
16
16
17
17
18
18
19
19
20
20
21
21
22
22
23
23
24
24
25
25
26
26
27
27
28
28
29
29
30
30
31
31
32
32
33
33
34
34
35
35
36
36
37
37
38
38
39
39
40
40
41
41
42
42
43
43
44
44
45
45
46
46
47
47
48
48
49
19784335...

output:

result:

points 0.50 points  0.5

Test #8:

score: 3.5

Acceptable Answer

time: 1ms

memory: 3780kb

input:

output:

result:

points 0.50 points  0.5

Test #9:

score: 3.5

Acceptable Answer

time: 0ms

memory: 3776kb

input:

1978433568
50
49
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
10
10
11
11
12
12
13
13
14
14
15
15
16
16
17
17
18
18
19
19
20
20
21
21
22
22
23
23
24
24
25
25
26
26
27
27
28
28
29
29
30
30
31
31
32
32
33
33
34
34
35
35
36
36
37
37
38
38
39
39
40
40
41
41
42
42
43
43
44
44
45
45
46
46
47
47
48
48
49
19784335...

output:

result:

points 0.50 points  0.5

Test #10:

score: 3.5

Acceptable Answer

time: 1ms

memory: 4076kb

input:

output:

result:

points 0.50 points  0.5

Test #11:

score: 3.5

Acceptable Answer

time: 1ms

memory: 4052kb

input:

1978433568
50
49
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
10
10
11
11
12
12
13
13
14
14
15
15
16
16
17
17
18
18
19
19
20
20
21
21
22
22
23
23
24
24
25
25
26
26
27
27
28
28
29
29
30
30
31
31
32
32
33
33
34
34
35
35
36
36
37
37
38
38
39
39
40
40
41
41
42
42
43
43
44
44
45
45
46
46
47
47
48
48
49
19784335...

output:

result:

points 0.50 points  0.5

Test #12:

score: 3.5

Acceptable Answer

time: 1ms

memory: 3800kb

input:

1978433568
50
49
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
10
10
11
11
12
12
13
13
14
14
15
15
16
16
17
17
18
18
19
19
20
20
21
21
22
22
23
23
24
24
25
25
26
26
27
27
28
28
29
29
30
30
31
31
32
32
33
33
34
34
35
35
36
36
37
37
38
38
39
39
40
40
41
41
42
42
43
43
44
44
45
45
46
46
47
47
48
48
49
19784335...

output:

result:

points 0.50 points  0.5

Test #13:

score: 3.5

Acceptable Answer

time: 2ms

memory: 3824kb

input:

output:

result:

points 0.50 points  0.5

Test #14:

score: 3.5

Acceptable Answer

time: 2ms

memory: 4084kb

input:

output:

result:

points 0.50 points  0.5

Test #15:

score: 3.5

Acceptable Answer

time: 2ms

memory: 3824kb

input:

output:

result:

points 0.50 points  0.5

Test #16:

score: 3.5

Acceptable Answer

time: 1ms

memory: 3824kb

input:

output:

result:

points 0.50 points  0.5

Test #17:

score: 3.5

Acceptable Answer

time: 2ms

memory: 3820kb

input:

output:

result:

points 0.50 points  0.5

Test #18:

score: 3.5

Acceptable Answer

time: 4ms

memory: 3828kb

input:

output:

result:

points 0.50 points  0.5

Test #19:

score: 3.5

Acceptable Answer

time: 4ms

memory: 3796kb

input:

output:

result:

points 0.50 points  0.5

Test #20:

score: 3.5

Acceptable Answer

time: 4ms

memory: 3848kb

input:

output:

result:

points 0.50 points  0.5

Test #21:

score: 3.5

Acceptable Answer

time: 4ms

memory: 3908kb

input:

output:

result:

points 0.50 points  0.5

Test #22:

score: 3.5

Acceptable Answer

time: 2ms

memory: 4124kb

input:

output:

result:

points 0.50 points  0.5

Test #23:

score: 3.5

Acceptable Answer

time: 2ms

memory: 3824kb

input:

output:

result:

points 0.50 points  0.5

Test #24:

score: 3.5

Acceptable Answer

time: 3ms

memory: 3816kb

input:

output:

result:

points 0.50 points  0.5

Test #25:

score: 3.5

Acceptable Answer

time: 1ms

memory: 4044kb

input:

output:

result:

points 0.50 points  0.5

Test #26:

score: 3.5

Acceptable Answer

time: 1ms

memory: 3820kb

input:

output:

result:

points 0.50 points  0.5

Test #27:

score: 3.5

Acceptable Answer

time: 0ms

memory: 3772kb

input:

1978433568
50
49
10
15
15
46
15
29
4
29
14
29
10
35
10
49
15
18
8
10
19
29
0
10
8
32
8
38
35
44
29
41
30
32
27
38
29
31
15
28
9
14
7
32
21
29
1
19
19
23
18
33
6
27
4
40
27
34
31
47
4
17
11
21
3
41
22
32
39
41
20
46
14
26
27
37
16
17
27
42
4
36
12
17
7
25
8
43
9
13
44
48
2
15
2
45
5
38
17
24
19784335...

output:

result:

points 0.50 points  0.5

Test #28:

score: 0

Wrong Answer

time: 2ms

memory: 3812kb

input:

output:

result:

wrong answer Vertices 24 and 41 do have the same color, but they do not in returned answer

Subtask #3:

score: 16.5

Acceptable Answer

Test #34:

score: 16.5

Acceptable Answer

time: 1ms

memory: 3836kb

input:

output:

result:

points 0.50 points  0.5

Test #35:

score: 16.5

Acceptable Answer

time: 6ms

memory: 4096kb

input:

output:

result:

points 0.50 points  0.5

Test #36:

score: 16.5

Acceptable Answer

time: 6ms

memory: 3812kb

input:

output:

result:

points 0.50 points  0.5

Test #37:

score: 16.5

Acceptable Answer

time: 5ms

memory: 3836kb

input:

output:

result:

points 0.50 points  0.5

Test #38:

score: 16.5

Acceptable Answer

time: 2ms

memory: 3836kb

input:

output:

result:

points 0.50 points  0.5

Test #39:

score: 16.5

Acceptable Answer

time: 6ms

memory: 3836kb

input:

output:

result:

points 0.50 points  0.5

Test #40:

score: 16.5

Acceptable Answer

time: 5ms

memory: 3764kb

input:

output:

result:

points 0.50 points  0.5

Test #41:

score: 16.5

Acceptable Answer

time: 5ms

memory: 3808kb

input:

output:

result:

points 0.50 points  0.5

Test #42:

score: 16.5

Acceptable Answer

time: 5ms

memory: 3832kb

input:

output:

result:

points 0.50 points  0.5

Subtask #4:

score: 10.5

Acceptable Answer

Test #43:

score: 10.5

Acceptable Answer

time: 168ms

memory: 4828kb

input:

output:

result:

points 0.50 points  0.5

Test #44:

score: 10.5

Acceptable Answer

time: 158ms

memory: 4580kb

input:

output:

result:

points 0.50 points  0.5

Test #45:

score: 10.5

Acceptable Answer

time: 154ms

memory: 4872kb

input:

output:

result:

points 0.50 points  0.5

Test #46:

score: 10.5

Acceptable Answer

time: 154ms

memory: 4640kb

input:

output:

result:

points 0.50 points  0.5

Test #47:

score: 10.5

Acceptable Answer

time: 164ms

memory: 4864kb

input:

output:

result:

points 0.50 points  0.5

Test #48:

score: 10.5

Acceptable Answer

time: 159ms

memory: 4604kb

input:

output:

result:

points 0.50 points  0.5

Test #49:

score: 10.5

Acceptable Answer

time: 146ms

memory: 4576kb

input:

output:

result:

points 0.50 points  0.5

Test #50:

score: 10.5

Acceptable Answer

time: 143ms

memory: 4604kb

input:

output:

result:

points 0.50 points  0.5

Test #51:

score: 10.5

Acceptable Answer

time: 146ms

memory: 4572kb

input:

output:

result:

points 0.50 points  0.5

Subtask #5:

score: 0

Skipped

Dependency #1:

50%

Acceptable Answer