QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#374978 | #3051. Identity Function | SolitaryDream# | WA | 1ms | 3816kb | C++17 | 1.7kb | 2024-04-02 20:21:11 | 2024-04-02 20:21:12 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int N = 305;
int n;
const double NOT = -1e100;
const double INF = 1e100;
double w[N][N], lx[N], ly[N], slk[N];
int pre[N], vy[N], lk[N];
inline double Dis(pii a, pii b) {
return hypot(a.first - b.first, a.second - b.second);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout << fixed << setprecision(15);
cin >> n;
int x0, y0;
cin >> x0 >> y0;
for (int i = 0; i <= n; ++i) lk[i] = pre[i] = lx[i] = ly[i] = slk[i] = 0;
vector<pii> a(n + 1), b(n + 1);
double slen = 0;
for (int i = 1; i <= n; ++i) {
cin >> a[i].first >> a[i].second;
cin >> b[i].first >> b[i].second;
slen += Dis(a[i], b[i]);
}
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
w[i][j] = -Dis(a[i], b[j]);
for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) lx[i] = max(lx[i], w[i][j]);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) slk[j] = INF, vy[j] = 0;
int py = 0, p;
for (lk[py] = i; lk[py]; py = p) {
vy[py] = 1;
double d = INF;
int x = lk[py];
for (int y = 1; y <= n; ++y) if (!vy[y]) {
if (lx[x] + ly[y] - w[x][y] < slk[y]) slk[y] = lx[x] + ly[y] - w[x][y], pre[y] = py;
if (slk[y] < d) d = slk[y], p = y;
}
for (int y = 0; i <= n; ++i) if (vy[y]) lx[lk[y]] -= d, ly[y] += d; else slk[y] -= d;
}
for (; py; py = pre[py]) lk[py] = lk[pre[py]];
}
for (int i = 1; i <= n; ++i) {
slen -= lx[i] + ly[i];
}
cout << slen << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3816kb
input:
3
output:
0.000000000000000
result:
wrong answer 1st lines differ - expected: '1', found: '0.000000000000000'