QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#669240 | #9431. The Quest for El Dorado | mulberry | RE | 10ms | 3612kb | C++23 | 4.3kb | 2024-10-23 17:51:38 | 2024-10-23 17:51:39 |
Judging History
answer
// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
int T, n, m, k;
vector<array<int, 3>> g[N];
vector<int> mx[N][20];
void solve() {
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) g[i].clear();
for (int i = 1; i <= m; i++) {
int u, v, c, val;
cin >> u >> v >> c >> val;
g[u].push_back({v, c, val});
g[v].push_back({u, c, val});
}
vector<vector<pair<int, int>>> col(m + 1, vector<pair<int, int>>(1));
vector<pair<int, int>> info(k + 1);
vector<pair<int, int>> pos(k + 1);
for (int i = 1; i <= k; i++) {
int a, b;
cin >> a >> b;
info[i] = {a, b};
pos[i] = {a, col[a].size()};
col[a].push_back({i, b});
}
for (int i = 1; i <= m; i++) {
if (col[i].size() == 1) continue;
auto &a = col[i];
auto &v = mx[i];
for (int k = 0; k <= 18; k++) {
v[k].clear();
v[k].resize(a.size(), 0);
}
int n = a.size() - 1;
for (int j = 1; j < n; j++) v[0][j] = j + 1;
for (int k = 1; k <= 18; k++)
for (int j = 1; j <= n; j++) {
int l = v[k - 1][j], r = v[k - 1][min(n, j + (1 << (k - 1)))];
if (a[l].second < a[r].second)
v[k][j] = r;
else
v[k][j] = l;
}
}
vector<bool> vis(n + 1);
priority_queue<array<int, 3>> q;
q.push({0, 0, 1});
while (!q.empty()) {
auto [now, dis, x] = q.top();
q.pop();
if (vis[x]) continue;
vis[x] = 1;
for (auto [v, c, val] : g[x]) {
if (vis[v]) continue;
auto [C, Dis] = info[now];
if (c == C && dis + val <= Dis) {
q.push({now, dis + val, v});
} else {
if (col[c].size() == 1) continue;
auto find = [&](int x) {
auto &a = col[c];
int l = 1, r = a.size() - 1;
while (l + 1 < r) {
int mid = (l + r) / 2;
if (a[mid].first < x)
l = mid;
else
r = mid;
}
if (a[l].first >= x)
return l;
else if (a[r].first >= x)
return r;
return -1;
};
int st = find(now + 1);
if (st == -1) continue;
// cout << "debug1 " << now << ' ' << dis << ' ' << x << '\n';
// cout << "debug2 " << c << ' ' << st << ' ' <<
// col[c][st].first
// << ' ' << col[c][st].second << '\n';
// cout << "debug3 " << val << '\n';
auto query = [&](int x, int val) {
// cout << "before " << x << ' ' << col[c][x].second <<
// '\n';
auto &a = col[c];
auto &v = mx[c];
if (a[x].second >= val) return a[x].first;
for (int i = 18; i >= 0; i--) {
// cout << v[x][i] << ' ' << a.size() << '\n';
if (a[v[i][x]].second < val &&
x + (1 << i) < a.size()) {
x += (1 << i);
cout << x << '\n';
}
}
// cout << "after " << x << '\n';
if (a[v[0][x]].second >= val) return a[v[x][0]].first;
return -1;
};
int newpos = query(st, val);
if (newpos == -1) continue;
// cout << "newpos " << newpos << '\n';
assert(info[newpos].first == c);
assert(info[newpos].second >= val);
q.push({newpos, val, v});
}
}
}
for (int i = 1; i <= n; i++) {
if (vis[i])
cout << 1;
else
cout << 0;
}
cout << '\n';
}
signed 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: 10ms
memory: 3612kb
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
Runtime Error
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...