QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #634974 | #8232. Yet Another Shortest Path Query | LateRegistration# | ML | 2140ms | 714836kb | C++17 | 5.1kb | 2024-10-12 18:32:00 | 2024-10-12 18:32:03 |
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] = mp[j][i] = w;
}
}
for (auto [s, t, id, inc] : qs) {
if (mp[s].count(t)) {
res[id] = min(res[id], mp[s][t] + 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] = min(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]) {
for (auto [k, w2] : g[i]) {
for (auto [l, w3] : g[j]) {
if (mp[k].count(l)) {
int id = mp[k][l];
best[id] = min(best[id], w1 + w2 + w3);
}
if (mp[l].count(k)) {
int id = mp[l][k];
best[id] = min(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: 1ms
memory: 3568kb
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: 3628kb
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: 0
Accepted
time: 1786ms
memory: 693764kb
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:
ok 1000000 numbers
Test #4:
score: 0
Accepted
time: 2082ms
memory: 714836kb
input:
35479 70156 1 2 53094201 1 3 95796673 1 4 35585979 1 5 55612594 2 3 60766083 3 4 64392832 4 5 32896460 5 2 91649893 6 2 6196154 6 7 4986564 7 3 91799790 7 8 10909791 8 4 30034265 8 9 95672010 9 4 67004237 9 10 77872672 10 5 68900058 10 6 42927604 11 6 71288663 11 12 51597962 12 7 79690815 12 13 9742...
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:
ok 1000000 numbers
Test #5:
score: 0
Accepted
time: 2140ms
memory: 714360kb
input:
35811 70820 1 2 40434193 1 3 13483892 1 4 32864259 1 5 47591755 1 6 65123023 1 7 81695948 1 8 1102880 1 9 47223939 1 10 52947058 1 11 31439481 2 3 94162364 3 4 20590842 4 5 24137043 5 6 74926235 6 7 9376267 7 8 97130364 8 9 75568799 9 10 5022411 10 11 59066963 11 2 96177033 12 2 17823959 12 13 83906...
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:
ok 1000000 numbers
Test #6:
score: -100
Memory Limit Exceeded
input:
200000 599952 127401 69434 88680591 127401 39916 10673559 127401 52475 59546013 127401 77787 74018113 127401 11462 7023970 60723 37187 65141305 60723 115008 72307785 60723 71812 47362248 60723 143858 20042617 60723 153890 48502784 60723 172009 21754689 60723 23327 97998405 63817 58332 30056889 63817...
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 ...