QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#90425 | #5251. Constellations | jaker | WA | 2636ms | 298252kb | C++14 | 2.5kb | 2023-03-23 01:35:38 | 2023-03-23 01:35:40 |
Judging History
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'