QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#100399 | #5588. Eroding Pillars | PetroTarnavskyi | AC ✓ | 153ms | 11804kb | C++17 | 1.4kb | 2023-04-25 20:17:14 | 2023-04-25 20:17:16 |
Judging History
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++;
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]);
if (v != 0 && fup[i] >= tin[v]) {
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: 3724kb
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: 3620kb
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: 2ms
memory: 3560kb
input:
1 1000000000 -1000000000
output:
1414213562.3730950356
result:
ok found '1414213562.3730950', expected '1414213562.3730950', error '0.0000000'
Test #4:
score: 0
Accepted
time: 77ms
memory: 11752kb
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:
129014631.0649484694
result:
ok found '129014631.0649485', expected '129014631.0649485', error '0.0000000'
Test #5:
score: 0
Accepted
time: 119ms
memory: 11700kb
input:
999 -37 59 90 99 -78 -74 84 82 -33 22 -5 14 -37 -35 6 -97 -35 -91 -17 -55 85 -75 -13 9 -87 70 64 74 45 -74 -83 -71 -91 -69 64 -54 -28 37 98 65 28 32 12 83 21 94 -42 -63 -14 22 12 -91 -77 -82 18 -79 97 4 23 25 54 58 56 -39 -82 63 -15 89 -36 96 51 5 -37 54 99 57 5 68 82 -75 30 -71 -82 31 -36 -28 48 98...
output:
12.7279220614
result:
ok found '12.7279221', expected '12.7279221', error '0.0000000'
Test #6:
score: 0
Accepted
time: 124ms
memory: 11804kb
input:
999 23 -84 12 68 -82 94 66 -48 -51 21 -65 -75 -8 83 -23 96 7 -83 -5 30 -46 -39 84 81 -43 45 30 -22 66 -35 -40 1 50 37 -41 -56 18 2 88 -30 -15 -69 89 -16 -94 -40 -73 -63 69 -57 -94 -9 -7 -40 11 -23 -35 74 -82 87 -33 55 -60 37 -15 -68 -1 84 57 -5 -46 57 -30 75 -66 52 -60 49 -81 -56 79 0 14 84 -62 47 2...
output:
12.0415945788
result:
ok found '12.0415946', expected '12.0415946', error '0.0000000'
Test #7:
score: 0
Accepted
time: 78ms
memory: 11676kb
input:
997 689820909 872197007 378062710 -66574440 -176944532 -402500960 -626416632 489298754 -136800206 216455436 -778550826 662442290 791847147 -283748980 205140992 574212402 -942834097 -861224089 835282360 82261161 -580910695 909114837 718944957 -300196729 -345551018 -762335643 -341008263 775846670 8876...
output:
122351709.4959319681
result:
ok found '122351709.4959320', expected '122351709.4959320', error '0.0000000'
Test #8:
score: 0
Accepted
time: 86ms
memory: 11788kb
input:
997 208411906 -972635109 -98072108 457691541 -21432981 100025358 25260912 -117889920 133656678 -623760924 114370818 -533755956 175530188 -819179923 33595291 -156785555 213886197 -998183115 -39015831 182082508 -139507592 651066476 -129054888 602284739 -154761300 722253757 198647581 -927066054 1186318...
output:
17118003.7749864385
result:
ok found '17118003.7749864', expected '17118003.7749864', error '0.0000000'
Test #9:
score: 0
Accepted
time: 153ms
memory: 11680kb
input:
997 1000000000 499352126 945459590 1000000000 -771435961 1000000000 -1000000000 -350227738 -589254335 1000000000 905535137 1000000000 89248404 1000000000 -716290383 1000000000 -1000000000 -131547422 442941577 1000000000 -22966025 1000000000 -907816124 1000000000 178384700 1000000000 -783935630 -1000...
output:
1000001278.9881818295
result:
ok found '1000001278.9881818', expected '1000001278.9881818', error '0.0000000'
Test #10:
score: 0
Accepted
time: 0ms
memory: 5756kb
input:
4 1 1 -1 -1 1 -1 -1 1
output:
1.4142135624
result:
ok found '1.4142136', expected '1.4142136', error '0.0000000'