QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#702660#5251. ConstellationstreasuresgcWA 7ms53084kbC++232.1kb2024-11-02 16:21:442024-11-02 16:21:45

Judging History

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

  • [2024-11-02 16:21:45]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:53084kb
  • [2024-11-02 16:21:44]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
	int sum=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f*=-1;ch=getchar();}
	while(isdigit(ch)){sum=sum*10+ch-48;ch=getchar();}
	return sum*f;
}
int ord[2005][2005];
struct node{
	int x,y;
};
node P[2005];
int fa[5005];
int pfhx[5005],pfhy[5005];
int sumx[5005],sumy[5005];
int gs[5005];
int tot;
const double eps = 1e-7;
priority_queue<pair<double,pair<int,int> > > pq;
inline int find_father(int x)
{
	if(fa[x]!=x) return fa[x]=find_father(fa[x]);
	return x;
}
inline void unionn(int x,int y)
{
	int rx=find_father(x);
	int ry=find_father(y);
	if(rx==ry) return;
	cout<<gs[rx]+gs[ry]<<endl;
	tot++;
	fa[rx]=tot,fa[ry]=tot;
	pfhx[tot]=pfhx[rx]+pfhx[ry];
	pfhy[tot]=pfhy[rx]+pfhy[ry];
	sumx[tot]=sumx[rx]+sumx[ry];
	sumy[tot]=sumy[rx]+sumy[ry];
	gs[tot]=gs[rx]+gs[ry];
}
inline double dis(int x,int y)
{
	x=find_father(x),y=find_father(y);
	double dx = pfhx[x]+pfhx[y]-sumx[x]*sumx[y]*2;
	double dy = pfhy[x]+pfhy[y]-sumy[x]*sumy[y]*2;
	
	
	return (dx+dy) / (double)(gs[x]*gs[y]);
}
inline bool check_top()
{
	double g=-pq.top().first;
	int nx=-pq.top().second.first;
	int ny=-pq.top().second.second;
	pq.pop();
//	cout<<nx<<" "<<ny<<" "<<g<<endl;
//	system("pause");
	if(find_father(nx)==find_father(ny)) return 0;
	double d=dis(nx,ny);
//	cout<<nx<<" "<<ny<<" "<<g<<" "<<d<<endl;
//	system("pause");
	if(d <= g+eps && d >= g-eps)
	{
		unionn(nx,ny);
		return 1;
	}
	
	nx=find_father(nx);
	ny=find_father(ny);
	pq.push(make_pair( -d,make_pair(-min(nx,ny) , -max(nx,ny)) ));
	
	return 0;
}
signed main()
{
	int n;
	n=read();
	for(int i=1;i<=n;i++)P[i].x=read(),P[i].y=read();
	for(int i=1;i<=n;i++) fa[i]=i,sumx[i]=P[i].x,sumy[i]=P[i].y,pfhx[i]=P[i].x*P[i].x,pfhy[i]=P[i].y*P[i].y,gs[i]=1;
	for(int i=n+1;i<=2*n;i++) fa[i]=i;
	tot=n;
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
		{
			double d=dis(i,j);
			pq.push(make_pair(-d,make_pair(-i,-j)));
		}
	
	int T=n-1;
	while(T--)
		while(!check_top());
	
	return 0;
}


详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3636kb

input:

2
0 0
1 0

output:

2

result:

ok single line: '2'

Test #2:

score: -100
Wrong Answer
time: 7ms
memory: 53084kb

input:

2000
1000 -1000
1000 -999
1000 -998
1000 -997
1000 -996
1000 -995
1000 -994
1000 -993
1000 -992
1000 -991
1000 -990
1000 -989
1000 -988
1000 -987
1000 -986
1000 -985
1000 -984
1000 -983
1000 -982
1000 -981
1000 -980
1000 -979
1000 -978
1000 -977
1000 -976
1000 -975
1000 -974
1000 -973
1000 -972
1000...

output:

2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
10...

result:

wrong answer 2nd lines differ - expected: '2', found: '3'