QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #562759 | #8673. 最短路径 | guosoun | 0 | 2431ms | 174688kb | C++17 | 2.1kb | 2024-09-13 20:34:39 | 2024-09-13 20:34:40 |
Judging History
answer
#include <bits/stdc++.h>
using ll = long long;
const int N = 2e5 + 10;
int main() {
std::cin.tie(0)->sync_with_stdio(0);
int n, m, q, seed;
std::vector<std::vector<std::pair<int, ll>>> g[2];
std::cin >> n >> m >> q >> seed;
g[0].resize(n + 1), g[1].resize(n + 1);
std::mt19937 gen(seed);
unsigned max = -1u / n * n;
auto sample = [&]() {
unsigned x;
do {
x = gen();
} while (x >= max);
return x % n + 1;
};
while (m--) {
int u = sample(), v = sample();
ll w = gen();
g[0][u].emplace_back(v, w), g[1][v].emplace_back(u, w);
}
for (int i = 1; i <= n; i++) {
for (int t : {0, 1})
std::sort(g[t][i].begin(), g[t][i].end(),
[&](auto a, auto b) { return a.second < b.second; });
}
static bool vis[2][N];
static ll dis[2][N];
int x = -1;
while (q--) {
int s, t;
std::cin >> s >> t;
memset(dis, 0x3f, sizeof(dis));
memset(vis, 0, sizeof(vis));
std::priority_queue<std::tuple<ll, int, std::vector<std::pair<int, ll>>::iterator>> pq[2];
if (g[0][s].size()) pq[0].emplace(g[0][s].begin()->second, s, g[0][s].begin()), vis[0][s] = 1;
if (g[1][t].size()) pq[1].emplace(g[1][t].begin()->second, t, g[1][t].begin()), vis[1][t] = 1;
for (int c = 0; g[0][s].size() || g[1][t].size(); c ^= 1) {
auto [d, u, it] = pq[c].top();
auto [v, w] = *it;
pq[c].pop();
if (std::next(it) != g[c][u].end()) pq[c].emplace(dis[c][u] + std::next(it)->second, u, std::next(it));
if (vis[c][v]) continue;
dis[c][v] = d, vis[c][v] = 1;
if (vis[c ^ 1][v]) {
x = v;
break;
}
if (g[c][v].size()) pq[c].emplace(d + g[c][v].begin()->second, v, g[c][v].begin());
}
if (x == -1) {
std::cout << -1 << '\n';
continue;
}
ll ans = dis[0][x] + dis[1][x];
for (int u = 1; u <= n; u++)
if (vis[0][u])
for (auto [v, w] : g[0][u])
if (vis[1][v]) ans = std::min(ans, dis[0][u] + w + dis[1][v]);
std::cout << ans << '\n';
}
}
/*
4 8 1 1112792816
2 3
*/
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 5
Accepted
time: 0ms
memory: 7072kb
input:
4 8 5 1112792816 2 3 4 3 4 3 3 2 1 4
output:
3419197189 1798364963 1798364963 3986398077 2337967903
result:
ok 5 lines
Test #2:
score: 0
Wrong Answer
time: 252ms
memory: 7352kb
input:
2000 2000 2000 3336994405 659 1650 1678 341 818 235 1380 1865 1927 1366 1233 1673 267 1698 775 1022 1255 1110 1533 1928 1854 169 1579 729 449 1335 943 583 360 50 795 926 1584 911 1924 604 280 309 1429 420 1107 1858 1466 76 265 1109 1077 622 245 1941 957 1434 1560 1128 122 51 229 925 826 1006 851 323...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
wrong answer 157th lines differ - expected: '787133140', found: '-1'
Subtask #2:
score: 0
Wrong Answer
Test #6:
score: 0
Wrong Answer
time: 2431ms
memory: 130572kb
input:
3000 3000000 10000 37461678 2873 1368 1757 2000 1262 1822 2484 1778 2055 2096 2545 366 2923 2028 1469 1874 691 631 1173 2967 894 2020 1207 881 373 236 1913 1923 1351 16 1066 2032 471 1561 1047 2043 457 145 2728 1752 2521 1199 1568 904 2515 543 1472 2161 748 2744 748 1908 912 172 2340 2494 977 267 10...
output:
4557430889146414377 4557430888930816348 4557430889077993379 982031438 898398200 3317527563 4557430889005573457 4557430889163804741 4557430889105607802 4557430888968014468 4295044742 3253452187 3330876309 4557430889175445016 4557430889012541364 4557430889159119057 4557430889065114618 4557430889192030...
result:
wrong answer 1st lines differ - expected: '36084543', found: '4557430889146414377'
Subtask #3:
score: 0
Runtime Error
Test #13:
score: 0
Runtime Error
input:
200000 200000 10000 1824322211 104482 112162 130667 13436 36792 142259 51832 97549 15358 180076 128251 92635 45296 195115 62109 38014 22014 86754 79735 103777 94797 96086 196760 5955 45622 59618 12995 62585 55686 156402 23085 68138 170749 148553 97603 160274 112975 22651 116322 190720 84774 57075 23...
output:
result:
Subtask #4:
score: 0
Wrong Answer
Test #17:
score: 0
Wrong Answer
time: 1391ms
memory: 42400kb
input:
200000 500000 10000 3113327438 68816 31422 174349 125983 18111 188786 84806 87249 142007 180723 95611 116398 104758 196349 77547 89859 120350 77199 110906 10209 177461 194861 115505 105566 27493 166237 15676 158290 86204 116010 159979 125659 132461 61989 194289 157721 18830 82910 166696 98162 125208...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
wrong answer 1st lines differ - expected: '21671419385', found: '-1'
Subtask #5:
score: 0
Runtime Error
Test #21:
score: 0
Runtime Error
input:
200000 500000 10000 1843053063 3409 108359 168924 184622 13119 119837 109492 38050 97152 51201 49047 12472 183998 191613 193074 177289 194248 104409 15509 88499 61967 143398 4532 56790 196650 158711 63655 70744 140178 107299 63530 87330 127334 159237 7134 184418 125289 28604 176966 179527 181695 128...
output:
result:
Subtask #6:
score: 0
Wrong Answer
Test #24:
score: 0
Wrong Answer
time: 1767ms
memory: 168164kb
input:
100000 3000000 10000 3892765041 14843 34156 43390 49542 38564 95501 26194 87126 18638 53346 69414 47011 95472 58303 44370 77172 75652 90555 94386 31888 47911 9905 70599 97061 52764 24896 31445 15589 82314 43852 97155 93412 11834 45082 75614 42459 67802 32024 82389 4968 32860 62514 97630 28012 14839 ...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
wrong answer 1st lines differ - expected: '1547972368', found: '-1'
Subtask #7:
score: 0
Wrong Answer
Test #33:
score: 0
Wrong Answer
time: 1918ms
memory: 174688kb
input:
200000 3000000 10000 3910662331 161257 40967 50546 86049 199665 199302 177403 36274 158790 143151 193304 78511 28032 149723 96394 37099 2157 76024 195400 34830 41933 147591 191613 96468 194837 67293 57992 63117 24749 6694 117818 87323 46130 53470 174812 24950 149173 124886 119910 54123 2297 124533 5...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
wrong answer 1st lines differ - expected: '3371897180', found: '-1'