QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#639413 | #6615. Cross the Maze | jty233 | WA | 1ms | 3872kb | C++23 | 5.7kb | 2024-10-13 19:25:46 | 2024-10-13 19:25:46 |
Judging History
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);
for(auto &[x, y] : players) {
cin >> x >> y;
}
for(auto &[x, y] : ropes) {
cin >> x >> y;
}
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; _++){
std::vector vis(a+1, std::vector<bool>(b+1, false));
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;
}
if(x != a || y != b){
moves[u] += 'S';
if(c+_>=l) fl = false;
}else{
moves[u] += 'P';
}
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;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3732kb
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: 3748kb
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: 3664kb
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: 3588kb
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: 3872kb
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: 3564kb
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: 3800kb
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: 3620kb
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: 3636kb
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: 3868kb
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: 3564kb
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: 1ms
memory: 3616kb
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: 3656kb
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: 3624kb
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: 3556kb
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: 3672kb
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: 3592kb
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: 1ms
memory: 3812kb
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: 1ms
memory: 3616kb
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: 3796kb
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 7 9 2 10 UUUUURPP 9 5 5 1 UUUULLLL 9 7 4 10 UUUUURRR 9 1 3 1 UUUUSSUU 4 1 4 1 PPPPPPPP 2 6 1 7 URPPPPPP
result:
ok answer 8
Test #21:
score: 0
Accepted
time: 0ms
memory: 3548kb
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: 3588kb
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: 3744kb
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: 0
Accepted
time: 1ms
memory: 3596kb
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 78 1 68 LLSSSLLLLLLLL 1 49 1 55 RRRRRRPPPPPPP 1 44 1 47 RRRPPPPPPPPPP 1 12 1 24 RRRRSRRRRRRRR 1 72 1 59 LLLLLLLLLLLLL 1 3 1 6 RRRPPPPPPPPPP 1 75 1 75 PPPPPPPPPPPPP 1 37 1 28 LLLLLLLLLPPPP 1 83 1 81 LLPPPPPPPPPPP 1 17 1 17 PPPPPPPPPPPPP
result:
ok answer 13
Test #25:
score: 0
Accepted
time: 1ms
memory: 3820kb
input:
10 1 100 1 43 1 75 1 59 1 42 1 26 1 33 1 88 1 7 1 24 1 95 1 68 1 31 1 39 1 74 1 66 1 67 1 28 1 70 1 86 1 58
output:
25 1 7 1 31 RRRRRRRRRRRRRRRRRRRRSRRRR 1 75 1 74 LPPPPPPPPPPPPPPPPPPPPPPPP 1 24 1 39 RRRSSSSSSSSSSRRRRRRRRRRRR 1 88 1 86 LLPPPPPPPPPPPPPPPPPPPPPPP 1 43 1 68 RRRRRRRRRRRRRRRRRRRRRRRRR 1 95 1 70 LLLLLLLLLLLLLLLLLLLLLLLLL 1 42 1 67 RRRRRRRRRRRRRRRRRRRRRRRRR 1 33 1 58 RRRRRRRRRRRRRRRRRRRRRRRRR 1 59 1 66 ...
result:
ok answer 25
Test #26:
score: 0
Accepted
time: 1ms
memory: 3736kb
input:
10 1 100 1 88 1 38 1 43 1 99 1 63 1 24 1 44 1 31 1 47 1 52 1 6 1 14 1 55 1 15 1 82 1 57 1 73 1 74 1 97 1 51
output:
23 1 31 1 14 LLLLLLLLLLLLLLLLLPPPPPP 1 88 1 82 LLLLLLPPPPPPPPPPPPPPPPP 1 47 1 51 RRRRPPPPPPPPPPPPPPPPPPP 1 38 1 15 LLLLLLLLLLLLLLLLLLLLLLL 1 52 1 74 RRRRRRRRRRRRRRRRRRRRSRR 1 44 1 57 RRRRRRRRRRRRRPPPPPPPPPP 1 43 1 55 RRRRRRRRRRRRPPPPPPPPPPP 1 24 1 6 LLLLLLLLLLLLLLLLLLPPPPP 1 99 1 97 LLPPPPPPPPPPPPPP...
result:
ok answer 23
Test #27:
score: 0
Accepted
time: 1ms
memory: 3576kb
input:
10 100 1 6 1 96 1 41 1 76 1 97 1 72 1 94 1 82 1 23 1 40 1 31 1 33 1 84 1 77 1 41 1 24 1 39 1 68 1 8 1 82 1
output:
35 94 1 84 1 UUUUUUUUUUPPPPPPPPPPPPPPPPPPPPPPPPP 23 1 24 1 DPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP 76 1 41 1 UUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUU 72 1 39 1 UUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUPP 41 1 33 1 UUUUUUUUPPPPPPPPPPPPPPPPPPPPPPPPPPP 82 1 82 1 PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP 6 1 8 1 DDPPPPPPPPPPP...
result:
ok answer 35
Test #28:
score: 0
Accepted
time: 1ms
memory: 3600kb
input:
10 100 1 19 1 23 1 29 1 11 1 44 1 87 1 68 1 56 1 35 1 34 1 34 1 63 1 40 1 90 1 8 1 69 1 81 1 41 1 18 1 82 1
output:
28 19 1 18 1 UPPPPPPPPPPPPPPPPPPPPPPPPPPP 23 1 40 1 DDDDDDDDDDDDDDDDDPPPPPPPPPPP 29 1 41 1 DDDDDDDDDDDDPPPPPPPPPPPPPPPP 11 1 8 1 UUUPPPPPPPPPPPPPPPPPPPPPPPPP 44 1 69 1 DDDDDDDDDDDDDDDDDDDDDDDDDPPP 87 1 90 1 DDDPPPPPPPPPPPPPPPPPPPPPPPPP 68 1 82 1 DDDDDDDDDDDDDDPPPPPPPPPPPPPP 56 1 81 1 DDDDDDDDDDDDDDD...
result:
ok answer 28
Test #29:
score: -100
Wrong Answer
time: 1ms
memory: 3820kb
input:
10 100 1 42 1 4 1 64 1 31 1 92 1 45 1 60 1 24 1 8 1 35 1 57 1 70 1 42 1 17 1 72 1 51 1 56 1 87 1 52 1 88 1
output:
34 64 1 87 1 DDDDDDDDDDDDDDDDDDDDDDDPPPPPPPPPPP 24 1 57 1 DDDDDDDDDDDDDDDDDDDDDDDDDDSDDDDDDD 92 1 88 1 UUUUPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP 35 1 52 1 DDDDDDDDDDDDDDDSSSSSSSSSSSSSSSSSDD 42 1 70 1 DDDDDDDDDDDDDDDDDDDDDDDDDDDDPPPPPP 4 1 17 1 DDDDDDDDDDDDDPPPPPPPPPPPPPPPPPPPPP 31 1 56 1 DDDDDDDDDDDDDDDDDD...
result:
wrong answer move to the same cell