QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#809971	#9241. Sphinx	hhy0613	12	224ms	4816kb	C++17	2.2kb	2024-12-11 18:46:16	2024-12-11 18:46:21

Judging History

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

[2024-12-11 18:46:21]
评测

测评结果：12
用时：224ms
内存：4816kb

查看

[2024-12-11 18:46:16]
提交

answer

#include "sphinx.h"
#include<bits/stdc++.h>
using namespace std;
const int N=255;
int n,g[N][N],fa[N],Fa[N];
int find(int x){return (fa[x]==x?x:fa[x]=find(fa[x]));}
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);}
void Merge(int x,int y){Fa[Find(x)]=Find(y);}
vector<int> node[N];
int calc(const vector<int>& E){
	for(int i=0;i<n;++i) Fa[i]=i;
	for(int i=0;i<n;++i){
		for(int j=0;j<n;++j){
			if(E[i]==n && E[j]==n && g[i][j]==1) Merge(i,j); 
		}
	}
	int ans=0;
	for(int i=0;i<n;++i){
		if(E[i]==n && Fa[i]==i) ++ans;
	}
	return ans;
}
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) && u!=v) E[v]=n;
		}
		for(int i=0;i<n;++i) node[i].clear();
		for(int i=0;i<n;++i) node[find(i)].push_back(i);
		int tar=0;
		for(int i=0;i<n;++i){
			if(fa[i]==i){
				for(int v:node[i]){
					if(E[v]!=n){
						++tar;
						break;
					}
				} 
			}
		}
		if(perform_experiment(E)==tar+calc(E)) 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;
				if(perform_experiment(F)==(int)vev.size()-mid+1+calc(F)) r=mid;
				else{
					ans=mid;
					l=mid+1;
				}
			}
			assert(ans!=-1);
			merge(u,vev[ans]);
			tar=0;
			for(int i=0;i<n;++i){
				if(fa[i]==i && E[i]!=n) ++tar;
			}
			if(perform_experiment(E)==tar+calc(E)) break;
		}
	}
#ifndef HHY
	vector<int> res(n);
	int tot=0;
	for(int i=0;i<n;++i){
		if(fa[i]==i) res[i]=tot++;
	}
	for(int i=0;i<n;++i) res[i]=res[find(i)];
	return res;
#endif
}

源文件, 语言: C++17

詳細信息

Subtask #1:

score: 1.5

Acceptable Answer

Test #1:

score: 3

Accepted

time: 0ms

memory: 4044kb

input:

output:

result:

ok #experiments: 4

Test #2:

score: 3

Accepted

time: 0ms

memory: 4064kb

input:

output:

result:

ok #experiments: 2

Test #3:

score: 1.5

Acceptable Answer

time: 1ms

memory: 4064kb

input:

output:

result:

points 0.50 points  0.5

Test #4:

score: 1.5

Acceptable Answer

time: 1ms

memory: 4124kb

input:

output:

result:

points 0.50 points  0.5

Subtask #2:

score: 0

Runtime Error

Dependency #1:

50%

Acceptable Answer

Test #5:

score: 0

Runtime Error

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:

Subtask #3:

score: 0

Runtime Error

Test #34:

score: 0

Runtime Error

input:

output:

result:

Subtask #4:

score: 10.5

Acceptable Answer

Test #43:

score: 10.5

Acceptable Answer

time: 103ms

memory: 4560kb

input:

output:

result:

points 0.50 points  0.5

Test #44:

score: 10.5

Acceptable Answer

time: 159ms

memory: 4504kb

input:

output:

result:

points 0.50 points  0.5

Test #45:

score: 10.5

Acceptable Answer

time: 186ms

memory: 4568kb

input:

output:

result:

points 0.50 points  0.5

Test #46:

score: 10.5

Acceptable Answer

time: 224ms

memory: 4592kb

input:

output:

result:

points 0.50 points  0.5

Test #47:

score: 10.5

Acceptable Answer

time: 196ms

memory: 4816kb

input:

output:

result:

points 0.50 points  0.5

Test #48:

score: 10.5

Acceptable Answer

time: 161ms

memory: 4616kb

input:

output:

result:

points 0.50 points  0.5

Test #49:

score: 10.5

Acceptable Answer

time: 126ms

memory: 4792kb

input:

output:

result:

points 0.50 points  0.5

Test #50:

score: 10.5

Acceptable Answer

time: 79ms

memory: 4584kb

input:

output:

result:

points 0.50 points  0.5

Test #51:

score: 10.5

Acceptable Answer

time: 29ms

memory: 4812kb

input:

output:

result:

points 0.50 points  0.5

Subtask #5:

score: 0

Skipped

Dependency #1:

50%

Acceptable Answer

QOJ.ac

QOJ

Judging History

answer

詳細信息

Subtask #1:

Test #1:

input:

output:

result:

Test #2:

input:

output:

result:

Test #3:

input:

output:

result:

Test #4:

input:

output:

result:

Subtask #2:

Dependency #1:

Test #5:

input:

output:

result:

Subtask #3:

Test #34:

input:

output:

result:

Subtask #4:

Test #43:

input:

output:

result:

Test #44:

input:

output:

result:

Test #45:

input:

output:

result:

Test #46:

input:

output:

result:

Test #47:

input:

output:

result:

Test #48:

input:

output:

result:

Test #49:

input:

output:

result:

Test #50:

input:

output:

result:

Test #51:

input:

output:

result:

Subtask #5:

Dependency #1:

Dependency #2: