QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#660339 | #9431. The Quest for El Dorado | LateRegistration# | WA | 89ms | 5048kb | C++20 | 2.3kb | 2024-10-20 10:31:22 | 2024-10-20 10:31:24 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
template <class comp = less<>> struct rmq {
vector<vector<int>> st;
rmq(const vector<int> &arr) : st(__lg(arr.size()) + 1) {
st[0] = arr;
for (int k = 1; k < st.size(); k++) {
st[k] = st[k - 1];
for (int i = 0; i + (1 << k) <= st[k].size(); i++) {
int x = st[k - 1][i + (1 << (k - 1))];
st[k][i] = comp()(st[k][i], x) ? st[k][i] : x;
}
}
}
int query(int l, int r) {
int k = __lg(r - l + 1);
int x = st[k][l], y = st[k][r - (1 << k) + 1];
return comp()(x, y) ? x : y;
}
};
void solve() {
int n, m, k;
cin >> n >> m >> k;
vector<vector<tuple<int, int, int>>> adj(n);
for (int i = 0; i < m; i++) {
int u, v, c, l;
cin >> u >> v >> c >> l;
u--, v--, c--;
adj[u].emplace_back(v, c, l);
adj[v].emplace_back(u, c, l);
}
vector<int> a(k), b(k);
vector<vector<int>> pos(m);
for (int i = 0; i < k; i++) {
cin >> a[i] >> b[i];
pos[--a[i]].push_back(i);
}
vector<int> bs, start(m);
for (int i = 0; i < m; i++) {
start[i] = bs.size();
for (int j : pos[i]) {
bs.push_back(b[j]);
}
}
rmq<greater<>> rmq_b(bs);
vector<array<int, 2>> dist(n, {k, 0});
priority_queue<pair<array<int, 2>, int>, vector<pair<array<int, 2>, int>>, greater<>> pq;
pq.emplace(dist[0] = {0, 0}, 0);
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d != dist[u]) continue;
auto [id, used] = d;
for (auto [v, c, l] : adj[u]) {
if (a[id] != c || b[id] - used < l) {
auto it = lower_bound(pos[c].begin(), pos[c].end(), id + 1);
if (it != pos[c].end()) {
int lb = pos[c].begin() - it, rb = pos[c].size() - 1, p = pos[c].size();
while (lb <= rb) {
int mid = (lb + rb) / 2;
if (rmq_b.query(start[c] + lb, start[c] + mid) >= l) {
rb = mid - 1;
p = mid;
} else {
lb = mid + 1;
}
}
if (p < pos[c].size() && dist[v] > array{*it, p}) {
pq.emplace(dist[v] = {*it, p}, v);
}
}
} else if (dist[v] > array{id, used + l}) {
pq.emplace(dist[v] = {id, used + l}, v);
}
}
}
for (int i = 0; i < n; i++) {
cout.put(dist[i][0] == k ? '0' : '1');
}
cout << "\n";
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int T;
cin >> T;
while (T--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3608kb
input:
2 5 6 4 1 2 1 30 2 3 1 50 2 5 5 50 3 4 6 10 2 4 5 30 2 5 1 40 1 70 6 100 5 40 1 30 3 1 1 2 3 1 10 1 100
output:
11011 100
result:
ok 2 lines
Test #2:
score: -100
Wrong Answer
time: 89ms
memory: 5048kb
input:
1110 46 80 30 44 23 5 46 10 28 1 64 32 34 3 40 9 36 1 26 15 14 5 95 38 19 2 34 2 17 4 183 10 38 2 81 5 15 2 83 31 38 3 100 40 30 1 53 41 10 1 193 29 20 5 18 14 41 3 78 8 16 5 74 46 13 3 78 44 28 3 45 1 40 3 133 5 32 1 108 22 26 2 83 10 38 1 77 11 40 1 11 17 21 2 66 41 46 3 98 9 36 2 25 40 18 1 19 27...
output:
1111000111100111110110000010110010111111110010 1000000010101001011011000000001000000100001000 1000000000000000000000000000000000000000000000 1011010000000010000100010011000100000000000010 1100000000000000000000101000010000001011000011 1001100010010000100101100000100001001010110 100010000000000000000...
result:
wrong answer 1st lines differ - expected: '1000110011110111110010100001010100100101000000', found: '1111000111100111110110000010110010111111110010'