QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#100374#5588. Eroding PillarsPetroTarnavskyiWA 60ms11604kbC++171.5kb2023-04-25 18:44:472023-04-25 18:44:50

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-25 18:44:50]
  • 评测
  • 测评结果:WA
  • 用时:60ms
  • 内存:11604kb
  • [2023-04-25 18:44:47]
  • 提交

answer

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

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define FOR(i, a, b) for (int i = (a); i<(b); ++i)
#define RFOR(i, b, a) for (int i = (b)-1; i>=(a); --i)
#define MP make_pair
#define PB push_back
#define F first
#define S second

typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;

const int MAX = 1 << 10;

int n;
int x[MAX], y[MAX];
LL d[MAX][MAX];
int timer;
int tin[MAX], fup[MAX];
bool used[MAX];
bool ok;

void dfs(int v, int p, LL m) {
	used[v] = true;
	tin[v] = fup[v] = timer++;
	int cnt = 0, mn = n + 1;
	FOR(i, 0, n) {
		if (d[v][i] <= m && i != p) {
			if (used[i]) {
				fup[v] = min(fup[v], tin[i]);
			}
			else {
				dfs(i, v, m);
				fup[v] = min(fup[v], fup[i]);
				mn = min(mn, fup[i]);
				cnt++;
			}
		}
	}
	fup[v] = min(fup[v], mn);
	if (v != 0 && mn >= tin[v] && cnt > 0) {
		ok = false;
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	n++;
	FOR(i, 1, n) {
		cin >> x[i] >> y[i];
	}
	FOR(i, 0, n) {
		FOR(j, 0, n) {
			d[i][j] = (LL)(x[j] - x[i]) * (x[j] - x[i]) + (LL)(y[j] - y[i]) * (y[j] - y[i]);
		}
	}
	LL l = 0, r = 2.1e18;
	while (r - l > 1) {
		LL m = (l + r) / 2;
		FOR(i, 0, n) {
			used[i] = false;
		}
		timer = 0;
		ok = true;
		dfs(0, -1, m);
		FOR(i, 0, n) {
			ok &= used[i];
		}
		if (ok) {
			r = m;
		}
		else {
			l = m;
		}
	}
	cout << fixed << setprecision(10) << sqrt(r) << "\n";
	return 0;
}

详细

Test #1:

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

input:

2
1 1
1 0

output:

1.4142135624

result:

ok found '1.4142136', expected '1.4142136', error '0.0000000'

Test #2:

score: 0
Accepted
time: 2ms
memory: 3748kb

input:

8
1 1
0 1
1 0
2 0
0 2
2 1
1 2
2 2

output:

1.0000000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #3:

score: 0
Accepted
time: 1ms
memory: 3680kb

input:

1
1000000000 -1000000000

output:

1414213562.3730950356

result:

ok found '1414213562.3730950', expected '1414213562.3730950', error '0.0000000'

Test #4:

score: -100
Wrong Answer
time: 60ms
memory: 11604kb

input:

1000
-197140284 703496508
105426106 -447628446
-321789030 -547969163
-275840107 -183856400
977079157 55081681
562400795 -99876434
-833457368 849631307
427777786 981882
-477648368 423363280
-986742316 -207582454
546089414 986224147
648775399 760817052
-111756907 833096696
-702954343 -487408110
-20831...

output:

119442679.3374826908

result:

wrong answer 1st numbers differ - expected: '129014631.0649485', found: '119442679.3374827', error = '0.0741928'