QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#639373#6615. Cross the Mazejty233WA 1ms3816kbC++235.7kb2024-10-13 19:12:462024-10-13 19:12:46

Judging History

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

  • [2024-10-13 19:12:46]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3816kb
  • [2024-10-13 19:12:46]
  • 提交

answer

#include "bits/stdc++.h"

using ll = long long;

struct MCFGraph {
    struct Edge {
        int v, c;
        double f;
        Edge(int v, int c, double f) : v(v), c(c), f(f) {}
    };
    const int n;
    std::vector<Edge> e;
    std::vector<std::vector<int>> g;
    std::vector<double> h, dis;
    std::vector<int> pre;
    bool dijkstra(int s, int t) {
        dis.assign(n, std::numeric_limits<double>::max());
        pre.assign(n, -1);
        std::priority_queue<std::pair<double, int>, std::vector<std::pair<double, int>>, std::greater<>> que;
        dis[s] = 0;
        que.emplace(0, s);
        while (!que.empty()) {
            double d = que.top().first;
            int u = que.top().second;
            que.pop();
            if (dis[u] < d) continue;
            for (int i : g[u]) {
                int v = e[i].v;
                int c = e[i].c;
                double f = e[i].f;
                if (c > 0 && dis[v] > d + h[u] - h[v] + f) {
                    dis[v] = d + h[u] - h[v] + f;
                    pre[v] = i;
                    que.emplace(dis[v], v);
                }
            }
        }
        return dis[t] != std::numeric_limits<double>::max();
    }
    MCFGraph(int n) : n(n), g(n) {}
    void addEdge(int u, int v, int c, int f) {
        g[u].push_back(e.size());
        e.emplace_back(v, c, f);
        g[v].push_back(e.size());
        e.emplace_back(u, 0, -f);
    }
    std::pair<int, double> flow(int s, int t) {
        int flow = 0;
        double cost = 0;
        h.assign(n, 0);
        while (dijkstra(s, t)) {
            for (int i = 0; i < n; ++i) h[i] += dis[i];
            int aug = std::numeric_limits<int>::max();
            for (int i = t; i != s; i = e[pre[i] ^ 1].v) aug = std::min(aug, e[pre[i]].c);
            for (int i = t; i != s; i = e[pre[i] ^ 1].v) {
                e[pre[i]].c -= aug;
                e[pre[i] ^ 1].c += aug;
            }
            flow += aug;
            cost += double(aug) * h[t];
        }
        return std::make_pair(flow, cost);
    }
};

std::vector<std::pair<int, int>> players, ropes;
using std::cin, std::cout;

int h_dis(const std::pair<int, int> &a, const std::pair<int, int> &b) {
    return std::abs(a.first - b.first) + std::abs(a.second - b.second);
}

double e_dis(const std::pair<int, int> &a, const std::pair<int, int> &b) {
    return std::sqrt((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second));
}

bool check(int mid, std::vector<std::pair<int, int>> &ans) {
    MCFGraph g(players.size() * 2 + 5);
    std::vector<std::tuple<int, int, int>> edge_id;
    edge_id.reserve(players.size() * ropes.size());
    for(int i = 0; i < players.size(); i++) {
        for(int j = 0; j < ropes.size(); j++) {
            if(h_dis(players[i], ropes[j]) > mid) {
                continue;
            }
            edge_id.emplace_back(i, j, g.e.size());
            g.addEdge(i, j + players.size(), 1, e_dis(players[i], ropes[j]));
        }
    }
    int s = players.size() * 2;
    int t = s + 1;
    for(int i = 0; i < players.size(); i++) {
        g.addEdge(s, i, 1, 0);
        g.addEdge(i + players.size(), t, 1, 0);
    }
    auto [flow, cost] = g.flow(s, t);
    if(flow != players.size()) {
        return false;
    } else {
        ans.clear();
        for(auto &[u, v, id] : edge_id) {
            if(g.e[id].c == 0) {
                ans.emplace_back(u, v);
            }
        }
        return true;
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, a, b;
    cin >> n >> a >> b;
    players.resize(n);
    ropes.resize(n);
    std::vector maze(a+1, std::vector<bool>(b+1, false));
    for(auto &[x, y] : players) {
        cin >> x >> y;
    }
    for(auto &[x, y] : ropes) {
        cin >> x >> y;
        // maze[x][y] = true;
    }
    std::vector<std::pair<int, int>> match;
    int l = 0, r = a + b;
    while(l < r) {
        int mid = (l + r) >> 1;
        if(check(mid, match)) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    cout << l << std::endl;
    std::vector<std::string> moves(n);
    auto pp = players;
    std::mt19937 eng(std::random_device{}());
    for(int _=0; _<l; _++){
        auto vis = maze;
        auto ppp = pp;
        bool fl = true;
        for(auto[u, v] : match) {
            auto&[x, y] = ppp[u];
            auto[a, b] = ropes[v];
            auto c = std::abs(x-a) + std::abs(y-b);

            if(x > a && !vis[x-1][y]) {
                moves[u] += 'U';
                x--;
                goto nxt;
            }
            if(y > b && !vis[x][y-1]) {
                moves[u] += 'L';
                y--;
                goto nxt;
            }
            if(x < a && !vis[x+1][y]) {
                moves[u] += 'D';
                x++;
                goto nxt;
            }
            if(y < b && !vis[x][y+1]) {
                moves[u] += 'R';
                y++;
                goto nxt;
            }
            moves[u] += 'P';
            if(x != a || y != b && c+_>=l){
                fl = false;
            }
            nxt:;
            vis[x][y] = true;
        }
        if(!fl){
            _--;
            for(int j=0; j<n; j++) moves[j].pop_back();
            std::shuffle(match.begin(), match.end(), eng);
            continue;
        }
        swap(ppp, pp);
    }
    for(auto[u, v] : match) {
        auto[x, y] = players[u];
        auto[a, b] = ropes[v];
        std::cout << x << ' ' << y << ' '
        << a << ' ' << b << ' ' << moves[u] << '\n';
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3604kb

input:

3 4 4
1 1
1 4
4 4
1 3
2 3
2 4

output:

2
1 1 1 3 RR
1 4 2 3 LD
4 4 2 4 UU

result:

ok answer 2

Test #2:

score: 0
Accepted
time: 0ms
memory: 3660kb

input:

3 2 2
1 1
1 2
2 2
1 1
2 1
2 2

output:

1
1 1 2 1 D
1 2 1 1 L
2 2 2 2 P

result:

ok answer 1

Test #3:

score: 0
Accepted
time: 0ms
memory: 3620kb

input:

2 3 3
1 1
1 3
1 2
2 2

output:

2
1 1 1 2 RP
1 3 2 2 DL

result:

ok answer 2

Test #4:

score: 0
Accepted
time: 0ms
memory: 3804kb

input:

2 10 10
2 9
3 8
10 5
10 10

output:

10
2 9 10 10 DDDDDDDDRP
3 8 10 5 LLLDDDDDDD

result:

ok answer 10

Test #5:

score: 0
Accepted
time: 0ms
memory: 3804kb

input:

6 10 10
4 9
4 2
3 6
10 1
10 10
4 1
6 8
5 10
6 3
5 1
2 9
3 2

output:

5
4 9 2 9 UUPPP
4 2 6 3 DDRPP
3 6 6 8 DDDRR
10 1 5 1 UUUUU
10 10 5 10 UUUUU
4 1 3 2 URPPP

result:

ok answer 5

Test #6:

score: 0
Accepted
time: 0ms
memory: 3668kb

input:

8 10 10
5 1
6 8
6 3
6 4
3 10
9 5
6 7
4 1
3 8
7 3
1 2
8 6
5 8
7 6
9 4
4 1

output:

4
5 1 4 1 UPPP
6 8 5 8 UPPP
6 3 7 3 DPPP
6 4 8 6 DDRR
3 10 3 8 LLPP
9 5 9 4 LPPP
6 7 7 6 LDPP
4 1 1 2 UUUR

result:

ok answer 4

Test #7:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

1 10 10
8 3
8 4

output:

1
8 3 8 4 R

result:

ok answer 1

Test #8:

score: 0
Accepted
time: 0ms
memory: 3656kb

input:

1 10 10
10 1
6 6

output:

9
10 1 6 6 UUUURRRRR

result:

ok answer 9

Test #9:

score: 0
Accepted
time: 0ms
memory: 3596kb

input:

8 10 10
7 8
4 6
10 9
4 7
4 3
10 6
3 3
2 7
3 7
2 10
3 8
1 9
6 1
3 10
10 2
6 4

output:

7
7 8 3 10 UUUURRP
4 6 2 10 UURRRRP
10 9 10 2 LLLLLLL
4 7 3 8 URPPPPP
4 3 6 1 LLDDPPP
10 6 6 4 UUUULLP
3 3 3 7 RRRRPPP
2 7 1 9 URRPPPP

result:

ok answer 7

Test #10:

score: 0
Accepted
time: 0ms
memory: 3660kb

input:

1 10 10
10 3
2 6

output:

11
10 3 2 6 UUUUUUUURRR

result:

ok answer 11

Test #11:

score: 0
Accepted
time: 0ms
memory: 3660kb

input:

3 10 10
7 8
4 4
3 1
7 10
6 7
2 4

output:

5
7 8 7 10 RRPPP
4 4 6 7 DDRRR
3 1 2 4 URRRP

result:

ok answer 5

Test #12:

score: 0
Accepted
time: 0ms
memory: 3656kb

input:

9 10 10
6 4
1 7
2 1
5 6
10 8
3 5
9 9
9 2
4 9
5 3
3 2
6 9
2 2
9 4
7 8
2 8
1 1
4 8

output:

5
6 4 3 2 UUULL
1 7 2 8 DRPPP
2 1 1 1 UPPPP
5 6 5 3 LLLPP
10 8 7 8 UUUPP
3 5 2 2 ULLLP
9 9 6 9 UUUPP
9 2 9 4 RRPPP
4 9 4 8 LPPPP

result:

ok answer 5

Test #13:

score: 0
Accepted
time: 0ms
memory: 3580kb

input:

2 10 10
9 8
3 3
5 8
4 9

output:

7
9 8 5 8 UUUUPPP
3 3 4 9 DRRRRRR

result:

ok answer 7

Test #14:

score: 0
Accepted
time: 0ms
memory: 3804kb

input:

8 10 10
10 5
8 4
2 8
2 4
10 8
6 6
1 7
10 1
8 6
10 5
10 2
5 9
8 10
10 4
3 9
4 2

output:

4
10 5 10 5 PPPP
8 4 10 4 DDPP
2 8 5 9 DDDR
2 4 4 2 LLDD
10 8 8 10 UURR
6 6 8 6 DDPP
1 7 3 9 DDRR
10 1 10 2 RPPP

result:

ok answer 4

Test #15:

score: 0
Accepted
time: 0ms
memory: 3732kb

input:

1 10 10
1 9
2 10

output:

2
1 9 2 10 DR

result:

ok answer 2

Test #16:

score: 0
Accepted
time: 0ms
memory: 3744kb

input:

8 10 10
5 10
3 8
2 8
3 5
4 2
8 2
7 9
3 4
8 9
9 6
3 6
10 2
4 10
10 6
6 5
5 5

output:

6
5 10 8 9 LDDDPP
3 8 4 10 DRRPPP
2 8 3 6 LLDPPP
3 5 6 5 DDDPPP
4 2 10 2 DDDDDD
8 2 10 6 DDRRRR
7 9 9 6 LLLDDP
3 4 5 5 DDRPPP

result:

ok answer 6

Test #17:

score: 0
Accepted
time: 0ms
memory: 3664kb

input:

1 10 10
8 6
1 8

output:

9
8 6 1 8 UUUUUUURR

result:

ok answer 9

Test #18:

score: 0
Accepted
time: 0ms
memory: 3816kb

input:

10 10 10
7 10
4 4
9 10
5 7
10 7
4 1
1 5
6 7
6 4
5 3
5 7
1 9
1 6
8 3
5 1
10 8
2 6
4 2
3 10
3 1

output:

5
7 10 3 10 UUUUP
4 4 3 1 ULLLP
9 10 10 8 LLDPP
5 7 1 6 UUUUL
10 7 5 7 UUUUU
4 1 5 1 DPPPP
1 5 1 9 RRRRP
6 7 2 6 UUUUL
6 4 8 3 LDDPP
5 3 4 2 ULPPP

result:

ok answer 5

Test #19:

score: 0
Accepted
time: 0ms
memory: 3736kb

input:

7 10 10
4 5
1 5
6 5
9 6
5 5
9 3
1 10
10 6
6 2
5 1
2 7
8 1
7 10
6 3

output:

6
4 5 5 1 LLLLDP
1 5 2 7 DRRPPP
6 5 6 3 LLPPPP
9 6 10 6 DPPPPP
5 5 6 2 LLLDPP
9 3 8 1 ULLPPP
1 10 7 10 DDDDDD

result:

ok answer 6

Test #20:

score: 0
Accepted
time: 0ms
memory: 3612kb

input:

6 10 10
9 7
4 1
9 1
7 9
2 6
9 5
5 1
4 1
2 10
4 10
3 1
1 7

output:

8
2 6 1 7 URPPPPPP
9 7 4 10 UUUUURRR
9 1 3 1 UUUUUUPP
9 5 5 1 UUUULLLL
7 9 2 10 UUUUURPP
4 1 4 1 PPPPPPPP

result:

ok answer 8

Test #21:

score: 0
Accepted
time: 0ms
memory: 3816kb

input:

10 10 10
7 7
8 6
10 3
6 2
10 8
1 10
9 5
1 2
8 3
10 9
8 9
8 10
6 4
7 8
4 3
3 5
3 9
6 1
8 7
10 2

output:

5
7 7 7 8 RPPPP
8 6 8 7 RPPPP
10 3 10 2 LPPPP
6 2 4 3 UURPP
10 8 8 9 UURPP
1 10 3 9 LDDPP
9 5 6 4 UUULP
1 2 3 5 DDRRR
8 3 6 1 UULLP
10 9 8 10 UURPP

result:

ok answer 5

Test #22:

score: 0
Accepted
time: 0ms
memory: 3752kb

input:

10 10 10
2 9
1 2
3 9
6 9
3 3
9 2
2 4
5 8
1 6
4 9
1 10
6 10
3 6
2 5
4 2
7 3
10 2
9 1
2 9
5 8

output:

8
2 9 2 9 PPPPPPPP
1 2 7 3 DDDDDDRP
3 9 1 10 RUUPPPPP
6 9 6 10 RPPPPPPP
3 3 9 1 LLDDDDDD
9 2 10 2 DPPPPPPP
2 4 4 2 LLDDPPPP
5 8 5 8 PPPPPPPP
1 6 2 5 LDPPPPPP
4 9 3 6 ULLLPPPP

result:

ok answer 8

Test #23:

score: 0
Accepted
time: 0ms
memory: 3548kb

input:

10 10 10
10 6
9 2
7 7
7 3
6 8
5 4
2 10
1 1
5 9
4 6
5 1
9 9
9 1
7 6
3 2
4 8
7 7
9 7
3 1
6 10

output:

4
10 6 9 7 URPP
9 2 9 1 LPPP
7 7 7 7 PPPP
7 3 5 1 UULL
6 8 9 9 DDDR
5 4 3 2 UULL
2 10 4 8 LLDD
1 1 3 1 DDPP
5 9 6 10 DRPP
4 6 7 6 DDDP

result:

ok answer 4

Test #24:

score: -100
Wrong Answer
time: 1ms
memory: 3616kb

input:

10 1 100
1 17
1 49
1 12
1 37
1 83
1 44
1 75
1 78
1 72
1 3
1 75
1 47
1 55
1 81
1 6
1 59
1 17
1 68
1 28
1 24

output:

13
1 3 1 6 RRRPPPPPPPPPP
1 83 1 81 LLPPPPPPPPPPP
1 49 1 55 RRRRRRPPPPPPP
1 12 1 24 RRRRPRRRRRRRR
1 78 1 68 LLPPPLLLLLLLL
1 75 1 75 PPPPPPPPPPPPP
1 72 1 59 LLLLLLLLLLLLL
1 44 1 47 RRRPPPPPPPPPP
1 37 1 28 LLLLLLLLLPPPP
1 17 1 17 PPPPPPPPPPPPP

result:

wrong answer back to maze