QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#660912 | #2804. Travel Guide | AngelOlan | AC ✓ | 188ms | 22972kb | C++20 | 2.3kb | 2024-10-20 13:55:00 | 2024-10-20 13:55:07 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
constexpr int INF = 1e9;
struct STree {
#define ls (k<<1)+1
#define rs (k<<1)+2
#define lp ls, s, m
#define rp rs, m, e
int n;
vector<int> st;
STree(int n) : n(n), st((n << 2) + 5, INF) {}
int comb(int x, int y) { return min(x, y); }
void upd(int k, int s, int e, int i, int x) {
if (s + 1 == e) {
st[k] = x;
return;
}
int m = (s + e) >> 1;
if (i < m) {
upd(lp, i, x);
} else {
upd(rp, i, x);
}
st[k] = comb(st[ls], st[rs]);
}
void upd(int i, int x) { return upd(0, 0, n, i, x); }
int query(int k, int s, int e, int a, int b) {
if (s >= a && e <= b) {
return st[k];
}
int m = (s + e) >> 1, ans = INF;
if (a < m) {
ans = comb(ans, query(lp, a, b));
}
if (b > m) {
ans = comb(ans, query(rp, a, b));
}
return ans;
}
int query(int a, int b) { return query(0, 0, n, a, b); }
};
signed main() {
cin.tie(0)->sync_with_stdio(0);
int n, m;
cin >> n >> m;
vector<vector<pair<int, int>>> g(n);
while (m--) {
int u, v, w;
cin >> u >> v >> w;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
vector<vector<int>> d(3, vector(n, INF));
for (int i = 0; i < 3; ++i) {
priority_queue<pair<int, int>> pq;
pq.push({0, i});
d[i][i] = 0;
while (!pq.empty()) {
auto [du, u] = pq.top();
pq.pop();
du = -du;
if (du > d[i][u]) {
continue;
}
for (auto &[v, w] : g[u]) {
if (du + w < d[i][v]) {
d[i][v] = du + w;
pq.push({-d[i][v], v});
}
}
}
}
vector<int> v;
for (int i = 0; i < n; ++i) {
v.push_back(d[0][i]);
v.push_back(d[1][i]);
v.push_back(d[2][i]);
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
auto get = [&](int x) -> int {
return lower_bound(v.begin(), v.end(), x) - v.begin();
};
map<array<int, 3>, int> mp;
for (int i = 0; i < n; ++i) {
++mp[{get(d[0][i]), get(d[1][i]), get(d[2][i])}];
}
STree st(v.size());
int ans = 0;
for (auto &[a, cnt] : mp) {
auto [x, y, z] = a;
if (z < st.query(0, y + 1)) {
ans += cnt;
st.upd(y, z);
}
}
cout << ans << '\n';
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3564kb
input:
5 4 0 3 1 1 3 1 2 3 1 4 3 1
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3828kb
input:
5 6 0 3 1 1 3 1 2 3 1 4 3 1 0 1 1 0 2 1
output:
3
result:
ok single line: '3'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
20 55 3 13 74 1 3 72 1 15 63 0 15 62 0 14 59 2 14 56 2 19 80 11 19 83 6 11 70 6 10 74 10 17 67 7 17 77 7 9 87 9 18 97 12 18 78 4 12 70 4 5 83 5 16 85 8 16 86 8 13 72 14 19 60 0 19 99 0 18 80 8 18 90 5 8 88 3 16 77 3 12 86 2 12 67 2 10 56 9 10 66 9 11 66 7 11 90 7 15 58 4 15 71 1 4 94 1 13 70 13 17 1...
output:
7
result:
ok single line: '7'
Test #4:
score: 0
Accepted
time: 2ms
memory: 3884kb
input:
1020 3051 104 230 52 48 104 87 48 959 90 330 959 89 300 330 53 237 300 65 237 631 65 106 631 95 106 317 71 317 586 98 22 586 59 22 52 95 52 310 52 310 535 88 153 535 98 153 271 84 249 271 96 249 450 84 410 450 82 410 565 83 497 565 55 497 817 88 191 817 80 191 1015 94 887 1015 81 63 887 72 63 694 50...
output:
46
result:
ok single line: '46'
Test #5:
score: 0
Accepted
time: 3ms
memory: 4236kb
input:
2020 6051 0 3 55 1 3 87 2 3 68 0 4 97 1 4 54 2 4 70 0 5 85 1 5 82 2 5 60 0 6 72 1 6 79 2 6 99 0 7 91 1 7 60 2 7 72 0 8 77 1 8 97 2 8 91 0 9 74 1 9 81 2 9 55 0 10 89 1 10 68 2 10 58 0 11 77 1 11 73 2 11 77 0 12 99 1 12 84 2 12 84 0 13 100 1 13 81 2 13 91 0 14 99 1 14 86 2 14 92 0 15 59 1 15 89 2 15 8...
output:
24
result:
ok single line: '24'
Test #6:
score: 0
Accepted
time: 4ms
memory: 4432kb
input:
3020 9051 0 3 69 1 3 79 2 3 77 0 4 59 1 4 92 2 4 53 0 5 82 1 5 66 2 5 80 0 6 81 1 6 70 2 6 83 0 7 93 1 7 94 2 7 90 0 8 79 1 8 50 2 8 58 0 9 92 1 9 84 2 9 88 0 10 80 1 10 50 2 10 79 0 11 85 1 11 76 2 11 88 0 12 77 1 12 100 2 12 66 0 13 94 1 13 77 2 13 50 0 14 76 1 14 91 2 14 71 0 15 70 1 15 94 2 15 9...
output:
17
result:
ok single line: '17'
Test #7:
score: 0
Accepted
time: 3ms
memory: 4212kb
input:
4020 4019 3 4 1 4 5 1 5 6 1 6 7 1 7 8 1 8 9 1 9 10 1 10 11 1 11 12 1 12 13 1 13 14 1 14 15 1 15 16 1 16 17 1 17 18 1 18 19 1 19 20 1 20 21 1 21 22 1 22 23 1 23 24 1 24 25 1 25 26 1 26 27 1 27 28 1 28 29 1 29 30 1 30 31 1 31 32 1 32 33 1 33 34 1 34 35 1 35 36 1 36 37 1 37 38 1 38 39 1 39 40 1 40 41 1...
output:
4020
result:
ok single line: '4020'
Test #8:
score: 0
Accepted
time: 186ms
memory: 22972kb
input:
100000 299995 18590 70777 73 18590 38536 90 38536 76091 79 44089 76091 50 44089 87529 90 35020 87529 71 29584 35020 94 29584 58488 90 52722 58488 62 50591 52722 71 50591 90548 83 53254 90548 57 34039 53254 53 34039 53760 69 53760 99114 74 57559 99114 92 41590 57559 86 37055 41590 95 10215 37055 98 1...
output:
129
result:
ok single line: '129'
Test #9:
score: 0
Accepted
time: 188ms
memory: 22952kb
input:
100000 299997 26930 58529 99 33412 58529 76 33412 46143 97 37829 46143 91 37829 49817 58 49817 82123 100 82123 96015 97 77840 96015 59 39112 77840 56 39112 77682 92 74407 77682 68 34674 74407 56 34674 97957 58 43202 97957 52 29849 43202 85 29849 71498 100 9984 71498 83 9984 79204 84 79204 92285 89 2...
output:
69
result:
ok single line: '69'
Test #10:
score: 0
Accepted
time: 120ms
memory: 19200kb
input:
100000 299991 0 3 95 1 3 55 2 3 64 0 4 52 1 4 60 2 4 92 0 5 57 1 5 82 2 5 61 0 6 73 1 6 77 2 6 82 0 7 52 1 7 74 2 7 52 0 8 94 1 8 68 2 8 61 0 9 96 1 9 78 2 9 81 0 10 93 1 10 51 2 10 70 0 11 83 1 11 71 2 11 75 0 12 71 1 12 76 2 12 83 0 13 64 1 13 86 2 13 65 0 14 53 1 14 65 2 14 61 0 15 95 1 15 70 2 1...
output:
8
result:
ok single line: '8'
Test #11:
score: 0
Accepted
time: 122ms
memory: 19272kb
input:
100000 299991 0 3 78 1 3 62 2 3 95 0 4 84 1 4 60 2 4 97 0 5 61 1 5 89 2 5 89 0 6 66 1 6 89 2 6 54 0 7 93 1 7 74 2 7 69 0 8 68 1 8 74 2 8 63 0 9 89 1 9 62 2 9 56 0 10 64 1 10 88 2 10 55 0 11 92 1 11 59 2 11 72 0 12 50 1 12 80 2 12 60 0 13 80 1 13 82 2 13 96 0 14 69 1 14 100 2 14 93 0 15 54 1 15 96 2 ...
output:
4
result:
ok single line: '4'
Test #12:
score: 0
Accepted
time: 78ms
memory: 18832kb
input:
100000 99999 3 4 1 4 5 1 5 6 1 6 7 1 7 8 1 8 9 1 9 10 1 10 11 1 11 12 1 12 13 1 13 14 1 14 15 1 15 16 1 16 17 1 17 18 1 18 19 1 19 20 1 20 21 1 21 22 1 22 23 1 23 24 1 24 25 1 25 26 1 26 27 1 27 28 1 28 29 1 29 30 1 30 31 1 31 32 1 32 33 1 33 34 1 34 35 1 35 36 1 36 37 1 37 38 1 38 39 1 39 40 1 40 4...
output:
100000
result:
ok single line: '100000'