QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#810810	#9241. Sphinx	hhy0613	43	223ms	5120kb	C++17	4.5kb	2024-12-12 11:17:23	2024-12-12 11:17:24

Judging History

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

[2024-12-12 11:17:24]
评测

测评结果：43
用时：223ms
内存：5120kb

查看

[2024-12-12 11:17:23]
提交

answer

#include "sphinx.h"
#include<bits/stdc++.h>
using namespace std;
const int N=255;
int n,g[N][N],fa[N],G[N][N],idx[N],C;
bool vis[N],S[N];
int find(int x){return (fa[x]==x?x:fa[x]=find(fa[x]));}
void merge(int x,int y){fa[find(x)]=find(y);}
vector<int> node[N];
void DFS(int u,const vector<int>& E){
	vis[u]=true;
	for(int v=0;v<n;++v){
		if(g[u][v]==1 && !vis[v] && ((E[u]==-1 && E[v]==-1 && find(u)==find(v)) || (E[u]==n && E[v]==n))) DFS(v,E);
	}
}
void dfs(int u,const vector<int>& E){
	vis[u]=true;
	for(int v=0;v<C;++v){
		if(G[u][v]==1 && !vis[v] && ((S[u] && S[v]) || (E[node[u][0]]==n && E[node[v][0]]==n))) dfs(v,E);
	}
}
vector<int> col;
void solve(){
	for(int x=0;x<n;++x){
		vector<int> E(n,-1);
		int tar=0;
		for(int u=0;u<C;++u){
			if(S[u]){
				for(int v:node[u]) E[v]=x;
			}else ++tar;
		}
		for(int i=0;i<C;++i) vis[i]=false;
		for(int i=0;i<C;++i){
			if(vis[i] || (!S[i] && E[node[i][0]]!=n)) continue;
			dfs(i,E);
			++tar;
		}
		if(perform_experiment(E)==tar) continue;
		while(true){
			vector<int> vev;
			for(int i=0;i<C;++i){
				if(!S[i] && col[node[i][0]]!=x) vev.push_back(i);
			}
			int l=0,r=(int)vev.size(),ans=-1;
			while(l<r){
				int mid=l+(r-l)/2;
				vector<int> F=E;
				for(int i=0;i<mid;++i){
					for(int u:node[vev[i]]) F[u]=n;
				}
				for(int i=0;i<C;++i) vis[i]=false;
				tar=0;
				for(int i=0;i<C;++i){
					if((F[node[i][0]]==n || F[node[i][0]]==x) && !vis[i]){
						dfs(i,F);
						++tar;
					}
				}
				if(perform_experiment(F)==(int)vev.size()-mid+tar) r=mid;
				else{
					ans=mid;
					l=mid+1;	
				}
			}
			assert(ans!=-1);
			for(int u:node[vev[ans]]) col[u]=x;
			tar=0;
			for(int i=0;i<C;++i){
				if(!S[i]){
					if(col[node[i][0]]==x){
						for(int u:node[i]) E[u]=n;
					}else ++tar;
				}
			}
			for(int i=0;i<C;++i) vis[i]=false;
			for(int i=0;i<C;++i){
				if(vis[i] || (!S[i] && E[node[i][0]]!=n)) continue;
				dfs(i,E);
				++tar;
			}
			if(perform_experiment(E)==tar) break;
		}
	}
}
vector<int> find_colours(int nn,vector<int> X,vector<int> Y){
	n=nn;
	memset(g,0,sizeof(g));
	for(int i=0;i<(int)X.size();++i) g[X[i]][Y[i]]=g[Y[i]][X[i]]=1;
	for(int i=0;i<n;++i) fa[i]=i;
	for(int u=0;u<n;++u){
		vector<int> E(n,-1);
		for(int v=0;v<n;++v){
			if(v>u || g[u][v]==0) E[v]=n;
		}
		E[u]=-1;
		for(int i=0;i<n;++i) vis[i]=false;
		int tar=0;
		for(int i=0;i<n;++i){
			if(vis[i]) continue;
			DFS(i,E);
			++tar;
		}
		if(perform_experiment(E)==tar) continue;
		while(true){
			for(int i=0;i<n;++i) node[i].clear();
			vector<int> vev;
			for(int i=0;i<n;++i) node[find(i)].push_back(i);
			for(int i=0;i<n;++i){
				if(i==find(u)) continue;
				for(int x:node[i]){
					if(x<=u && g[u][x]==1){
						vev.push_back(i);
						break;
					}
				}
			}
			int l=0,r=(int)vev.size(),ans=-1;
			while(l<r){
				int mid=l+(r-l)/2;
				vector<int> F(n,n);
				for(int j=mid;j<(int)vev.size();++j){
					for(int x:node[vev[j]]) F[x]=-1;
				}
				F[u]=-1;
				for(int i=0;i<n;++i) vis[i]=false;
				tar=0;
				for(int i=0;i<n;++i){
					if(vis[i]) continue;
					DFS(i,F);
					++tar;
				}
				if(perform_experiment(F)==tar) r=mid;
				else{
					ans=mid;
					l=mid+1;
				}
			}
			assert(ans!=-1);
			merge(u,vev[ans]);
			for(int i=0;i<n;++i) node[i].clear();
			for(int i=0;i<n;++i) node[find(i)].push_back(i);
			for(int v=0;v<n;++v){
				if(find(u)==find(v)){
					E[v]=-1;
					for(int t=0;t<n;++t){
						if(t<=u && g[t][v]==1) E[t]=-1;
					}
				}
			}
			for(int i=0;i<n;++i) vis[i]=false;
			tar=0;
			for(int i=0;i<n;++i){
				if(vis[i]) continue;
				DFS(i,E);
				++tar;
			}
			if(perform_experiment(E)==tar) break;
		}
	}
	C=0;
	for(int i=0;i<n;++i) node[i].clear();
	for(int i=0;i<n;++i){
		if(fa[i]==i){
			for(int j=0;j<n;++j){
				if(find(j)==i){
					idx[j]=C;
					node[C].push_back(j);
				}
			}
			++C;
		}
	}
	memset(G,0,sizeof(G));
	for(int i=0;i<n;++i){
		for(int j=0;j<n;++j){
			if(g[i][j]==1 && find(i)!=find(j)) G[idx[i]][idx[j]]=G[idx[j]][idx[i]]=1;
		}
	}
	if(C==1){
		int j=0;
		for(;j<n;++j){
			vector<int> E(n,-1);
			E[0]=j;
			if(perform_experiment(E)==1) break;
		}
		return vector<int>(n,j);
	}
	for(int i=0;i<C;++i) vis[i]=S[i]=false;
	vis[0]=S[0]=true;
	for(int v=0;v<C;++v){
		if(G[0][v]==1) vis[v]=true;
	}
	for(int i=1;i<C;++i){
		if(vis[i]) continue;
		vis[i]=S[i]=true;
		for(int v=0;v<C;++v){
			if(G[i][v]==1) vis[v]=true;
		}
	}
	col=vector<int>(n,-1);
	solve();
	for(int i=0;i<C;++i) S[i]^=1;
	solve();
	return col;
}

Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 3

Accepted

Test #1:

score: 3

Accepted

time: 0ms

memory: 4380kb

input:

output:

result:

ok #experiments: 5

Test #2:

score: 3

Accepted

time: 1ms

memory: 4316kb

input:

output:

result:

ok #experiments: 10

Test #3:

score: 3

Accepted

time: 1ms

memory: 4312kb

input:

output:

result:

ok #experiments: 10

Test #4:

score: 3

Accepted

time: 0ms

memory: 4324kb

input:

output:

result:

ok #experiments: 6

Subtask #2:

score: 7

Accepted

Dependency #1:

100%

Accepted

Test #5:

score: 7

Accepted

time: 3ms

memory: 4324kb

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:

ok #experiments: 173

Test #6:

score: 7

Accepted

time: 0ms

memory: 4584kb

input:

output:

result:

ok #experiments: 246

Test #7:

score: 7

Accepted

time: 3ms

memory: 4332kb

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:

ok #experiments: 254

Test #8:

score: 7

Accepted

time: 2ms

memory: 4324kb

input:

output:

result:

ok #experiments: 252

Test #9:

score: 7

Accepted

time: 3ms

memory: 4320kb

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:

ok #experiments: 266

Test #10:

score: 7

Accepted

time: 3ms

memory: 4316kb

input:

output:

result:

ok #experiments: 278

Test #11:

score: 7

Accepted

time: 4ms

memory: 4320kb

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:

ok #experiments: 432

Test #12:

score: 7

Accepted

time: 5ms

memory: 4400kb

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:

ok #experiments: 438

Test #13:

score: 7

Accepted

time: 0ms

memory: 4324kb

input:

output:

result:

ok #experiments: 444

Test #14:

score: 7

Accepted

time: 3ms

memory: 4392kb

input:

output:

result:

ok #experiments: 451

Test #15:

score: 7

Accepted

time: 4ms

memory: 4612kb

input:

output:

result:

ok #experiments: 430

Test #16:

score: 7

Accepted

time: 6ms

memory: 4628kb

input:

output:

result:

ok #experiments: 459

Test #17:

score: 7

Accepted

time: 0ms

memory: 4628kb

input:

output:

result:

ok #experiments: 163

Test #18:

score: 7

Accepted

time: 5ms

memory: 4636kb

input:

output:

result:

ok #experiments: 316

Test #19:

score: 7

Accepted

time: 5ms

memory: 4344kb

input:

output:

result:

ok #experiments: 334

Test #20:

score: 7

Accepted

time: 5ms

memory: 4416kb

input:

output:

result:

ok #experiments: 355

Test #21:

score: 7

Accepted

time: 5ms

memory: 4336kb

input:

output:

result:

ok #experiments: 399

Test #22:

score: 7

Accepted

time: 6ms

memory: 4332kb

input:

output:

result:

ok #experiments: 413

Test #23:

score: 7

Accepted

time: 6ms

memory: 4308kb

input:

output:

result:

ok #experiments: 448

Test #24:

score: 7

Accepted

time: 5ms

memory: 4628kb

input:

output:

result:

ok #experiments: 481

Test #25:

score: 7

Accepted

time: 4ms

memory: 4324kb

input:

output:

result:

ok #experiments: 382

Test #26:

score: 7

Accepted

time: 3ms

memory: 4612kb

input:

output:

result:

ok #experiments: 402

Test #27:

score: 7

Accepted

time: 4ms

memory: 4320kb

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:

ok #experiments: 432

Test #28:

score: 7

Accepted

time: 5ms

memory: 4388kb

input:

output:

result:

ok #experiments: 352

Test #29:

score: 7

Accepted

time: 6ms

memory: 4392kb

input:

output:

result:

ok #experiments: 417

Test #30:

score: 7

Accepted

time: 6ms

memory: 4340kb

input:

output:

result:

ok #experiments: 356

Test #31:

score: 7

Accepted

time: 6ms

memory: 4280kb

input:

output:

result:

ok #experiments: 425

Test #32:

score: 7

Accepted

time: 3ms

memory: 4328kb

input:

output:

result:

ok #experiments: 175

Test #33:

score: 7

Accepted

time: 4ms

memory: 4620kb

input:

output:

result:

ok #experiments: 468

Subtask #3:

score: 33

Accepted

Test #34:

score: 33

Accepted

time: 48ms

memory: 4320kb

input:

output:

result:

ok #experiments: 1250

Test #35:

score: 33

Accepted

time: 56ms

memory: 4344kb

input:

output:

result:

ok #experiments: 1252

Test #36:

score: 33

Accepted

time: 53ms

memory: 4412kb

input:

output:

result:

ok #experiments: 1266

Test #37:

score: 33

Accepted

time: 53ms

memory: 4340kb

input:

output:

result:

ok #experiments: 1281

Test #38:

score: 33

Accepted

time: 53ms

memory: 4292kb

input:

output:

result:

ok #experiments: 1432

Test #39:

score: 33

Accepted

time: 56ms

memory: 4312kb

input:

output:

result:

ok #experiments: 1724

Test #40:

score: 33

Accepted

time: 89ms

memory: 4348kb

input:

output:

result:

ok #experiments: 2391

Test #41:

score: 33

Accepted

time: 49ms

memory: 4336kb

input:

output:

result:

ok #experiments: 882

Test #42:

score: 33

Accepted

time: 129ms

memory: 4292kb

input:

output:

result:

ok #experiments: 2746

Subtask #4:

score: 0

Runtime Error

Test #43:

score: 21

Accepted

time: 129ms

memory: 4844kb

input:

output:

result:

ok #experiments: 1361

Test #44:

score: 21

Accepted

time: 162ms

memory: 4824kb

input:

output:

result:

ok #experiments: 1694

Test #45:

score: 21

Accepted

time: 195ms

memory: 4828kb

input:

output:

result:

ok #experiments: 1989

Test #46:

score: 21

Accepted

time: 223ms

memory: 5116kb

input:

output:

result:

ok #experiments: 2207

Test #47:

score: 21

Accepted

time: 211ms

memory: 5120kb

input:

output:

result:

ok #experiments: 2519

Test #48:

score: 21

Accepted

time: 205ms

memory: 4824kb

input:

output:

result:

ok #experiments: 2672

Test #49:

score: 0

Runtime Error

input:

output:

result:

Subtask #5:

score: 0

Skipped

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted

Dependency #3:

100%

Accepted