QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#90425#5251. ConstellationsjakerWA 2636ms298252kbC++142.5kb2023-03-23 01:35:382023-03-23 01:35:40

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-23 01:35:40]
  • 评测
  • 测评结果:WA
  • 用时:2636ms
  • 内存:298252kb
  • [2023-03-23 01:35:38]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i = j;i <= k;++i)
#define repp(i,j,k) for(int i = j;i >= k;--i)
#define pb push_back
#define mp make_pair
#define fr first
#define se second
#define P pair<int,int>
#define Pp pair< pair<double, pair<int,int> > , pair<int,int> >
#define time tim
int n;
struct node{
	int x,y;
}e[2010];
long long Dis[2010][2010];
int dis[2010][2010],f[2010],sz[2010],tim[2010];
set< pair< pair<double, pair<int,int> > , pair<int,int> > >s;
int get(int x) {
	if(f[x] != x) {
		f[x] = get(f[x]);
		return f[x];
	}
	else return f[x];
}
void merge(int x,int y,int ttt) {
	int fx = get(x) , fy = get(y);
	f[fy] = fx;
	sz[fx] += sz[fy]; 
	time[fx] = ttt;
}
void output_P(Pp x) {
	printf("*%.10lf %d %d\n",x.fr.fr,x.se.fr,x.se.se);
}
void insert(int id,int t) {
	rep(i,1,n) Dis[id][i] = 0 , Dis[i][id] = 0;
	rep(i,1,n) if(get(i) == id) {
		rep(j,1,n) if(get(j) != id) {
			int idd = get(j);
			Dis[ min(id,idd) ][ max(id,idd) ] += dis[i][j];
		}	
	}
	rep(i,1,n) if(get(i) == i && i != id) {
		s.insert( mp(  mp(1.0*Dis[ min(i,id) ][ max(i,id) ]/(sz[i]*sz[id]) , 
							mp( max( time[i] , time[id] ) , min( time[i] , time[id] ) ) 
						 ) , 
					   mp( min(i,id) , max(i,id) ) 
					) );
	}
}
void output() {
	printf("\n");
	set<Pp>::iterator it;
	for(it = s.begin();it != s.end();it++)
		printf("*%.10lf %d %d %d %d\n",it->fr.fr,it->fr.se.fr,it->fr.se.se,it->se.fr,it->se.se);
}
int main() {
//	freopen("1.in","r",stdin);
	scanf("%d",&n);
	rep(i,1,n) f[i] = i,sz[i] = 1,time[i] = i-n;
	rep(i,1,n) scanf("%d%d",&e[i].x,&e[i].y);
	rep(i,1,n) rep(j,i+1,n) {
		dis[i][j] = (e[i].x-e[j].x)*(e[i].x-e[j].x) + (e[i].y-e[j].y)*(e[i].y-e[j].y);
		dis[j][i] = dis[i][j];
		Dis[i][j] = dis[i][j];
		Dis[j][i] = dis[i][j];
		s.insert( mp( mp(dis[i][j], mp( time[j] , time[i] )  ) , mp(i,j) ) );
	}
	for(int ttt = 1;ttt < n;++ttt) {
		Pp x = (*s.begin());
		while( 1 ) {
			int id1 = get(x.se.fr) , id2 = get(x.se.se);
			if( ! (id1 == id2) && (1.0*Dis[min(id1,id2)][max(id1,id2)]/(sz[id1]*sz[id2]) == x.fr.fr) ) break;
			s.erase(s.begin()) , x = (*s.begin());
		}
		//printf("#%d %d %d %d %.10lf\n",x.se.fr,x.se.se,x.fr.se.fr,x.fr.se.se,x.fr.fr);
		merge( x.se.fr , x.se.se , ttt );
		int res = 0;
		rep(i,1,n) if( get(i) == x.se.fr ) res++;
		insert( x.se.fr , ttt );	
		printf("%d\n",res);
		if(ttt == 2)  {
		//	output();
		//	printf("#%lld\n",Dis[get(1)][get(3)]);
		}
	}
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 3612kb

input:

2
0 0
1 0

output:

2

result:

ok single line: '2'

Test #2:

score: -100
Wrong Answer
time: 2636ms
memory: 298252kb

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
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
...

result:

wrong answer 1938th lines differ - expected: '48', found: '0'