QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#374978#3051. Identity FunctionSolitaryDream#WA 1ms3816kbC++171.7kb2024-04-02 20:21:112024-04-02 20:21:12

Judging History

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

  • [2024-04-02 20:21:12]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3816kb
  • [2024-04-02 20:21:11]
  • 提交

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;
}

詳細信息

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'