QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#90357 | #5251. Constellations | jaker | WA | 2491ms | 298000kb | C++14 | 2.3kb | 2023-03-22 19:43:56 | 2023-03-22 19:43:59 |
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,int> , pair<int,int> >
int n;
struct node{
int x,y;
}e[2010];
long long Dis[2010][2010];
int dis[2010][2010],f[2010],sz[2010];
set< pair< pair<double,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 fx = get(x) , fy = get(y);
f[fy] = fx;
sz[fx] += sz[fy];
}
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]) , -t ) , 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\n",it->fr.fr,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;
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],0) , mp(i,j) ) );
}
//output();
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());
// if(ttt == 1999) printf("**%d\n",(int)(s.size()));
}
//printf("***\n");
//Delete( x.se.fr );
//Delete( x.se.se );
merge( x.se.fr , x.se.se );
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3776kb
input:
2 0 0 1 0
output:
2
result:
ok single line: '2'
Test #2:
score: -100
Wrong Answer
time: 2491ms
memory: 298000kb
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 1969th lines differ - expected: '80', found: '96'