QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#410508#5251. Constellationsucup-team1716#RE 2875ms191284kbC++142.1kb2024-05-14 06:14:342024-05-14 06:14:34

Judging History

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

  • [2024-05-14 06:14:34]
  • 评测
  • 测评结果:RE
  • 用时:2875ms
  • 内存:191284kb
  • [2024-05-14 06:14:34]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define int long long

typedef pair<int, int> pii;
typedef pair<double, pair<pii, pii> > Pair;
// distance, age old, age new, id old, id new

#define fi first
#define se second
#define mk make_pair

const int MAXN = 2000;

int n, X[MAXN + 5], Y[MAXN + 5];

int dist[MAXN + 5][MAXN + 5];

int fa[MAXN + 5], sz[MAXN + 5], age[MAXN + 5];

int getfa(int u) {
	if (fa[u] == u) {
		return u;
	}
	return fa[u] = getfa(fa[u]);
}

signed main() {
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> X[i] >> Y[i];
		fa[i] = i;
		sz[i] = 1;
		age[i] = -n + i; // the smaller this number, the older the constellation
	}
	
	set<Pair> s;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			dist[i][j] = (X[i] - X[j]) * (X[i] - X[j]) + (Y[i] - Y[j]) * (Y[i] - Y[j]);
			if (i < j) {
				s.insert(mk(dist[i][j], mk(mk(age[i], age[j]), mk(i, j))));
			}
		}
	}
	
	for (int t = 1; t <= n - 1; ++t) {
		Pair cur = *s.begin();
		s.erase(s.begin());
		int u = cur.se.se.fi;
		int v = cur.se.se.se;
		
		assert(getfa(u) == u);
		assert(getfa(v) == v);
		
		// merge u int v
		if (sz[u] > sz[v]) {
			swap(u, v);
		}
		
		for (int i = 1; i <= n; ++i) {
			if (getfa(i) == i && i != u && i != v) {
				if (age[u] < age[i]) { // u is older
					s.erase(mk((double)dist[u][i] / sz[u] / sz[i], mk(mk(age[u], age[i]), mk(u, i))));
				} else {
					s.erase(mk((double)dist[i][u] / sz[u] / sz[i], mk(mk(age[i], age[u]), mk(i, u))));
				}
				
				if (age[v] < age[i]) { // u is older
					s.erase(mk((double)dist[v][i] / sz[v] / sz[i], mk(mk(age[v], age[i]), mk(v, i))));
				} else {
					s.erase(mk((double)dist[i][v] / sz[v] / sz[i], mk(mk(age[i], age[v]), mk(i, v))));
				}
			}
		}
		
		sz[v] += sz[u];
		age[v] = t;
		
		for (int i = 1; i <= n; ++i) {
			if (getfa(i) == i && i != u && i != v) {
				
				dist[i][v] += dist[i][u];
				dist[v][i] += dist[u][i];
				
				s.insert(mk((double)dist[i][v] / sz[v] / sz[i], mk(mk(age[i], age[v]), mk(i, v)))); // i must be older than v
			}
		}
		
		fa[u] = v;
		
		cout << sz[v] << endl;
	}
	
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3504kb

input:

2
0 0
1 0

output:

2

result:

ok single line: '2'

Test #2:

score: 0
Accepted
time: 2875ms
memory: 191284kb

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:

ok 1999 lines

Test #3:

score: 0
Accepted
time: 2796ms
memory: 191260kb

input:

2000
-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
-971...

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:

ok 1999 lines

Test #4:

score: 0
Accepted
time: 2744ms
memory: 191264kb

input:

2000
-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 -10...

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:

ok 1999 lines

Test #5:

score: 0
Accepted
time: 2784ms
memory: 191196kb

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

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:

ok 1999 lines

Test #6:

score: -100
Runtime Error

input:

2000
1000 -250
1000 -249
1000 -248
1000 -247
1000 -246
1000 -245
1000 -244
1000 -243
1000 -242
1000 -241
1000 -240
1000 -239
1000 -238
1000 -237
1000 -236
1000 -235
1000 -234
1000 -233
1000 -232
1000 -231
1000 -230
1000 -229
1000 -228
1000 -227
1000 -226
1000 -225
1000 -224
1000 -223
1000 -222
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: