QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#553115	#9241. Sphinx	thomaswmy^#	28.5	160ms	4908kb	C++17	1.5kb	2024-09-08 09:11:11	2024-09-08 09:11:11

Judging History

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

[2024-09-08 09:11:11]
评测

测评结果：28.5
用时：160ms
内存：4908kb

查看

[2024-09-08 09:11:11]
提交

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) {
  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: 1ms

memory: 3780kb

input:

output:

result:

ok #experiments: 1

Test #2:

score: 3

Accepted

time: 1ms

memory: 3884kb

input:

output:

result:

ok #experiments: 1

Test #3:

score: 1.5

Acceptable Answer

time: 1ms

memory: 3872kb

input:

output:

result:

points 0.50 points  0.5

Test #4:

score: 1.5

Acceptable Answer

time: 1ms

memory: 3884kb

input:

output:

result:

points 0.50 points  0.5

Subtask #2:

score: 0

Runtime Error

Dependency #1:

50%

Acceptable Answer

Test #5:

score: 3.5

Acceptable Answer

time: 0ms

memory: 3812kb

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: 3816kb

input:

output:

result:

points 0.50 points  0.5

Test #7:

score: 3.5

Acceptable Answer

time: 1ms

memory: 4108kb

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: 0ms

memory: 4060kb

input:

output:

result:

points 0.50 points  0.5

Test #9:

score: 3.5

Acceptable Answer

time: 1ms

memory: 3812kb

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: 3820kb

input:

output:

result:

points 0.50 points  0.5

Test #11:

score: 3.5

Acceptable Answer

time: 0ms

memory: 3812kb

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: 4124kb

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

Runtime Error

input:

output:

result:

Subtask #3:

score: 16.5

Acceptable Answer

Test #34:

score: 16.5

Acceptable Answer

time: 5ms

memory: 3844kb

input:

output:

result:

points 0.50 points  0.5

Test #35:

score: 16.5

Acceptable Answer

time: 0ms

memory: 4140kb

input:

output:

result:

points 0.50 points  0.5

Test #36:

score: 16.5

Acceptable Answer

time: 5ms

memory: 3840kb

input:

output:

result:

points 0.50 points  0.5

Test #37:

score: 16.5

Acceptable Answer

time: 5ms

memory: 3784kb

input:

output:

result:

points 0.50 points  0.5

Test #38:

score: 16.5

Acceptable Answer

time: 5ms

memory: 3896kb

input:

output:

result:

points 0.50 points  0.5

Test #39:

score: 16.5

Acceptable Answer

time: 5ms

memory: 3828kb

input:

output:

result:

points 0.50 points  0.5

Test #40:

score: 16.5

Acceptable Answer

time: 5ms

memory: 3916kb

input:

output:

result:

points 0.50 points  0.5

Test #41:

score: 16.5

Acceptable Answer

time: 1ms

memory: 3820kb

input:

output:

result:

points 0.50 points  0.5

Test #42:

score: 16.5

Acceptable Answer

time: 5ms

memory: 3912kb

input:

output:

result:

points 0.50 points  0.5

Subtask #4:

score: 10.5

Acceptable Answer

Test #43:

score: 10.5

Acceptable Answer

time: 157ms

memory: 4604kb

input:

output:

result:

points 0.50 points  0.5

Test #44:

score: 10.5

Acceptable Answer

time: 160ms

memory: 4552kb

input:

output:

result:

points 0.50 points  0.5

Test #45:

score: 10.5

Acceptable Answer

time: 156ms

memory: 4864kb

input:

output:

result:

points 0.50 points  0.5

Test #46:

score: 10.5

Acceptable Answer

time: 155ms

memory: 4552kb

input:

output:

result:

points 0.50 points  0.5

Test #47:

score: 10.5

Acceptable Answer

time: 141ms

memory: 4908kb

input:

output:

result:

points 0.50 points  0.5

Test #48:

score: 10.5

Acceptable Answer

time: 153ms

memory: 4668kb

input:

output:

result:

points 0.50 points  0.5

Test #49:

score: 10.5

Acceptable Answer

time: 144ms

memory: 4664kb

input:

output:

result:

points 0.50 points  0.5

Test #50:

score: 10.5

Acceptable Answer

time: 159ms

memory: 4616kb

input:

output:

result:

points 0.50 points  0.5

Test #51:

score: 10.5

Acceptable Answer

time: 144ms

memory: 4600kb

input:

output:

result:

points 0.50 points  0.5

Subtask #5:

score: 0

Skipped

Dependency #1:

50%

Acceptable Answer