QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #634955 | #8232. Yet Another Shortest Path Query | LateRegistration# | WA | 1665ms | 692668kb | C++17 | 5.0kb | 2024-10-12 18:26:21 | 2024-10-12 18:26:25 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int n, m;
cin >> n >> m;
vector<set<pair<int, int>>> g(n);
while (m--) {
int u, v, w;
cin >> u >> v >> w;
u--, v--;
g[u].emplace(v, w);
g[v].emplace(u, w);
}
set<pair<int, int>> s;
for (int i = 0; i < n; i++) {
s.emplace(g[i].size(), i);
}
while (!s.empty()) {
auto [_, u] = *s.begin();
s.erase(s.begin());
for (auto [v, w] : g[u]) {
s.erase({g[v].size(), v});
g[v].erase({u, w});
s.emplace(g[v].size(), v);
}
}
int q;
cin >> q;
vector<int> res(q, INT_MAX);
vector<tuple<int, int, int, int>> qs;
vector<vector<tuple<int, int, int, int>>> q1(n), q2(n);
vector<unordered_map<int, int>> mp(n);
for (int i = 0; i < q; i++) {
int s, t;
cin >> s >> t;
s--, t--;
qs.emplace_back(s, t, i, 0);
}
auto rec = [&](auto self, int k, vector<tuple<int, int, int, int>> qs) -> void {
if (k == 1) {
for (int i = 0; i < n; i++) {
mp[i].clear();
}
for (int i = 0; i < n; i++) {
for (auto [j, w] : g[i]) {
mp[i][j] = w;
}
}
for (auto [s, t, id, inc] : qs) {
if (mp[s].count(t)) {
res[id] = min(res[id], mp[s][t] + inc);
} else if (mp[t].count(s)) {
res[id] = min(res[id], mp[t][s] + inc);
}
}
} else if (k == 2) {
vector<tuple<int, int, int, int>> nqs;
for (auto [s, t, id, inc] : qs) {
for (auto [x, w] : g[s]) {
nqs.emplace_back(x, t, id, inc + w);
}
for (auto [x, w] : g[t]) {
nqs.emplace_back(s, x, id, inc + w);
}
}
self(self, k - 1, nqs);
for (int i = 0; i < n; i++) {
mp[i].clear();
}
vector<int> pre(qs.size(), -1), best(qs.size(), INT_MAX);
for (int i = 0; i < qs.size(); i++) {
auto [s, t, id, inc] = qs[i];
if (!mp[s].count(t)) {
mp[s][t] = i;
} else {
pre[i] = mp[s][t];
}
}
for (int i = 0; i < n; i++) {
for (auto [j, w1] : g[i]) {
for (auto [k, w2] : g[i]) {
if (mp[j].count(k)) {
int id = mp[j][k];
best[id] = max(best[id], w1 + w2);
}
}
}
}
for (int i = 0; i < qs.size(); i++) {
if (pre[i] != -1) {
best[i] = best[pre[i]];
}
if (best[i] != INT_MAX) {
auto [s, t, id, inc] = qs[i];
res[id] = min(res[id], best[i] + inc);
}
}
} else if (k == 3) {
vector<tuple<int, int, int, int>> nqs;
for (auto [s, t, id, inc] : qs) {
for (auto [x, w] : g[s]) {
nqs.emplace_back(x, t, id, inc + w);
}
for (auto [x, w] : g[t]) {
nqs.emplace_back(s, x, id, inc + w);
}
}
self(self, k - 1, nqs);
for (int i = 0; i < n; i++) {
mp[i].clear();
}
vector<int> pre(qs.size(), -1), best(qs.size(), INT_MAX);
for (int i = 0; i < qs.size(); i++) {
auto [s, t, id, inc] = qs[i];
if (!mp[s].count(t)) {
mp[s][t] = i;
} else {
pre[i] = mp[s][t];
}
}
for (int i = 0; i < n; i++) {
for (auto [j, w1] : g[i]) {
if (i > j) continue;
for (auto [k, w2] : g[i]) {
for (auto [l, w3] : g[j]) {
if (mp[k].count(l)) {
int id = mp[k][l];
best[id] = max(best[id], w1 + w2 + w3);
}
}
}
}
}
for (int i = 0; i < qs.size(); i++) {
if (pre[i] != -1) {
best[i] = best[pre[i]];
}
if (best[i] != INT_MAX) {
auto [s, t, id, inc] = qs[i];
res[id] = min(res[id], best[i] + inc);
}
}
}
};
rec(rec, 1, qs);
rec(rec, 2, qs);
rec(rec, 3, qs);
for (int x : res) {
cout << (x == INT_MAX ? -1 : x) << "\n";
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3832kb
input:
6 9 1 2 4 2 3 6 3 6 5 6 5 3 5 4 2 4 1 3 3 4 9 1 3 100 5 3 1 5 1 3 1 6 3 4 3 5 2 5
output:
6 8 3 1 7
result:
ok 5 number(s): "6 8 3 1 7"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3868kb
input:
6 4 1 2 1 2 3 1 3 4 1 4 5 1 3 1 4 1 5 1 6
output:
3 -1 -1
result:
ok 3 number(s): "3 -1 -1"
Test #3:
score: -100
Wrong Answer
time: 1665ms
memory: 692668kb
input:
40005 79608 1 2 70031203 1 3 99924845 1 4 61645659 1 5 9324967 2 3 15761918 3 4 62534796 4 5 35260314 5 2 35948540 6 2 23727405 6 7 83302920 7 3 31010426 7 8 75060393 8 4 94275932 8 9 99663793 9 5 81701979 9 6 439297 10 6 46955645 10 11 89514237 11 7 21257310 11 12 53896253 12 8 67933315 12 13 26161...
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 7165th numbers differ - expected: '10951309', found: '46786556'