QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#719169 | #9431. The Quest for El Dorado | QSteve_Paul | TL | 630ms | 177124kb | C++23 | 4.5kb | 2024-11-06 23:01:08 | 2024-11-06 23:01:09 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
struct edge
{
int nei;
int c;
i64 l;
edge() = default;
edge(int nei, int c, i64 l) : nei(nei), c(c), l(l)
{
}
};
struct segment_tree
{
struct node
{
int l, r;
i64 val;
};
vector<node> a;
vector<i64> *b{};
vector<int> *idx{};
void build(int l, int r, int k = 1)
{
a[k].l = l;
a[k].r = r;
if (l == r)
{
a[k].val = (*idx)[l];
return;
}
int mid = (l + r) >> 1;
build(l, mid, k << 1);
build(mid + 1, r, k << 1 | 1);
update(a[k], a[k << 1], a[k << 1 | 1]);
}
void update(node &dest, const node &src1, const node &src2) const
{
if ((*b)[src1.val] > (*b)[src2.val])
dest.val = src1.val;
else
dest.val = src2.val;
}
node query(int l, int r, int k = 1)
{
if (l == a[k].l && r == a[k].r)
return a[k];
int mid = (a[k].l + a[k].r) >> 1;
if (r <= mid)
return query(l, r, k << 1);
else if (l >= mid + 1)
return query(l, r, k << 1 | 1);
node ans{};
ans.l = l;
ans.r = r;
update(ans, query(l, mid, k << 1), query(mid + 1, r, k << 1 | 1));
return ans;
}
};
void solve()
{
int n, m, k;
cin >> n >> m >> k;
vector<vector<edge>> g(n + 1);
for (int i = 1; i <= m; i++)
{
int u, v, c;
i64 l;
cin >> u >> v >> c >> l;
g[u].push_back({v, c, l});
g[v].push_back({u, c, l});
}
vector<int> a(k + 1);
vector<i64> b(k + 1);
for (int i = 1; i <= k; i++)
cin >> a[i] >> b[i];
vector<vector<int>> cidx(m + 1, vector<int>(1));
for (int i = 1; i <= k; i++)
cidx[a[i]].push_back(i);
vector<segment_tree> segs(m + 1);
for (int i = 1; i <= m; i++)
{
int cnt = int(cidx[i].size()) - 1;
segs[i].a.resize((cnt + 1) << 2);
segs[i].b = &b;
segs[i].idx = &(cidx[i]);
if (cnt == 0)
continue;
segs[i].build(1, cnt);
}
vector<int> vis(n + 1);
vector<pair<int, i64>> dist(n + 1, {k + 1, 0});
priority_queue<pair<pair<int, i64>, int>, vector<pair<pair<int, i64>, int>>, greater<>> pq;
pq.push({{0, 0}, 1});
dist[1] = {0, 0};
while (!pq.empty())
{
auto [d, node] = pq.top();
pq.pop();
if (vis[node])
continue;
vis[node] = 1;
for (const edge &e : g[node])
{
auto [nei, c, l] = e;
if (vis[nei])
continue;
if (c == a[d.first] && l + d.second <= b[d.first])
{
if (make_pair(d.first, l + d.second) < dist[nei])
{
dist[nei] = {d.first, l + d.second};
pq.push({dist[nei], nei});
}
}
else
{
if (cidx[c].size() == 1)
continue;
segment_tree &seg = segs[c];
int ll = upper_bound(cidx[c].begin() + 1, cidx[c].end(), d.first) - cidx[c].begin();
int L = ll;
if (ll == (int)cidx[c].size())
continue;
int rr = (int)cidx[c].size() - 1;
if (b[seg.query(L, rr).val] < l)
continue;
while (ll < rr)
{
int mid = (ll + rr) >> 1;
if (b[seg.query(L, mid).val] >= l)
rr = mid;
else
ll = mid + 1;
}
int idx = cidx[c][ll];
if (make_pair(idx, l) < dist[nei])
{
dist[nei] = {idx, l};
pq.push({dist[nei], nei});
}
}
}
}
for (int i = 1; i <= n; i++)
{
if (dist[i] != pair<int, i64>{k + 1, 0})
cout << 1;
else
cout << 0;
}
cout << "\n";
}
int main()
{
#ifdef lijn
freopen("/home/lijn/acm_practice/.build/input.in", "r", stdin);
freopen("/home/lijn/acm_practice/.build/output.out", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
cin >> t;
while (t--)
solve();
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3600kb
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: 0
Accepted
time: 134ms
memory: 7988kb
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:
1000110011110111110010100001010100100101000000 1100010010111011011011000000011000001100001000 1000000000000000000000000000000000000000000000 1011010000000010000100010011000100000000000010 1000000000000000000000101000010000001001000001 1001100010110000100001100000000011001110110 101010000000000000010...
result:
ok 1110 lines
Test #3:
score: 0
Accepted
time: 144ms
memory: 9068kb
input:
1110 41 95 66 37 16 1 93 8 38 13 61 41 25 7 10 40 26 13 90 18 34 12 84 29 21 7 22 32 41 10 52 20 17 18 273 41 31 2 163 17 11 20 316 24 14 7 35 1 5 7 39 26 38 13 48 10 15 14 154 4 7 12 8 13 6 20 139 18 9 10 90 16 33 7 54 9 35 5 39 36 31 17 9 10 20 17 74 37 34 13 6 7 9 9 153 12 7 18 173 5 7 3 194 21 3...
output:
11111010101111111011111111101111111111011 11111111111111111111111111111111111111101 11111111111111111111111111111111111111111 11011110111111111111111111111011111111111 10100010011110000001010100010110010000001 111111111111111111111111111111111111111111 100000000000100000000000000100100000000000 1000...
result:
ok 1110 lines
Test #4:
score: 0
Accepted
time: 333ms
memory: 123176kb
input:
1 200000 500000 179 94800 107033 1 16 64316 117022 8 184 105481 172922 2 53 37627 148708 9 37 179021 41825 10 29 177650 69319 5 20 144968 160008 6 68 54796 172626 2 201 35718 99731 3 127 45553 132280 2 433 199580 18097 1 116 77143 7273 7 90 49300 94594 8 231 52637 197546 8 62 156375 4265 2 54 136509...
output:
111111111011001111111110110111111100000111111111111011101111011111110011111111011111111101100111111111110100111111101111111111111111111111111111111111111111111101111111111111111101111101010111111111111111110111111110111110111011010001110111111111111101111110011111111111111111110110111101011111111111...
result:
ok single line: '111111111011001111111110110111...1110101101101111110110011110111'
Test #5:
score: 0
Accepted
time: 353ms
memory: 125468kb
input:
1 200000 500000 28600 134923 17846 1145 19 38550 190638 1881 173 153445 161902 1019 61 134582 132451 1259 32 27836 81432 1053 99 45363 165206 1879 453 173218 82373 1834 392 36060 180829 1434 93 158792 24019 1305 80 114091 131741 400 36 86750 83631 674 284 102965 26889 903 96 72980 92116 852 293 7814...
output:
100101111101011111011110111110111110111001110111001100100011001111111011111101111011111010111010010010011101100111101010111010011101011111110111111101110110110111111111000110110101011110111011110111011011001111111101111110011111010111110100111111001111010110110111101111111011111101001011101110111010...
result:
ok single line: '100101111101011111011110111110...0111111111111110001011011001011'
Test #6:
score: 0
Accepted
time: 278ms
memory: 137020kb
input:
1 500000 500000 132 33565 62505 9 27 159690 223311 5 72 136509 402294 1 30 335433 250256 8 32 46344 199283 1 53 101509 318328 1 91 154342 472216 1 98 219655 19442 6 8 488718 58652 1 64 88757 14212 1 51 92129 332927 10 69 418031 387995 5 1 433240 214628 1 67 402161 87957 2 84 107282 385626 3 86 18834...
output:
100100000001001001011000000000010101010000100000000011010010000010000001000000100010000000101010100000011010001000011111000000101001000010010100101010110100010011000000000010000000111010101010011001011100000011000010100000001000010000001000010000001100010100000000001000010001000000001100110000010110...
result:
ok single line: '100100000001001001011000000000...0100010000000010000000000001101'
Test #7:
score: 0
Accepted
time: 361ms
memory: 139980kb
input:
1 500000 500000 34800 356922 276405 1274 6 70376 56771 944 85 311347 288381 114 23 323396 269923 1542 25 403829 492566 1731 41 415774 97020 149 48 317081 340484 627 3 277226 227941 1804 69 349022 434891 1274 53 436085 437523 1274 83 110761 403042 1180 86 333338 341167 1274 88 4802 451135 1149 18 116...
output:
111001100110001100011110001011001010001111100000011100001101000011100110010111011011101111101110010101011111110000111101100111101010111111100110001011111111101111100010101001110001110100100111010011110111001100011000111011111111111110010100111001111010011000111001111111111100111010001110011011111010...
result:
ok single line: '111001100110001100011110001011...1101000100101011111011001110110'
Test #8:
score: 0
Accepted
time: 630ms
memory: 160696kb
input:
1 200000 500000 500000 138435 172074 2 320 40030 9389 6 35 61974 124326 6 64 4679 144065 8 238 47254 185524 1 74 138009 134825 8 235 164764 59275 5 227 134478 183172 7 69 131920 51571 3 140 119971 193848 6 98 130747 49642 9 376 67838 127653 1 30 32972 140348 4 1 39560 183382 10 15 151497 1703 4 274 ...
output:
101110010011111111000011100110111110111010011101100110001100101111001011100011100110011111001111111111100111111010000001011101011101111110111111110011110110111110000100101100111100101101001111111011001101110101101111100101101111110111100111110101001001010111100101101111100110110101001111101110110101...
result:
ok single line: '101110010011111111000011100110...1100010011101011101011101001011'
Test #9:
score: 0
Accepted
time: 405ms
memory: 161812kb
input:
1 200000 500000 500000 123878 17891 843 20144 35773 147691 427 7936 96800 135322 1787 8414 66660 124569 1948 30 103754 33455 1573 91 188810 189553 1180 89 106226 145102 1009 2028 77946 90544 33 7357 20000 127787 1284 6528 43787 82216 282 10 185497 15937 1211 12376 183320 77384 113 65 78356 71033 144...
output:
110101010101010111110011101111011001010000011001000100100000101100111101010000111101110110111010011011101110111010100110001110110110011011110101100100011100010110010010111000111011010100101011010100111000111010111010001001001001010110000000100111100010011110111100010011011100000011000101010100111001...
result:
ok single line: '110101010101010111110011101111...1011001110011011100011001010010'
Test #10:
score: 0
Accepted
time: 433ms
memory: 174376kb
input:
1 500000 500000 500000 426522 37213 5 70 324338 118732 7 21 455456 31351 1 25 269683 186562 3 92 297357 444426 9 81 326458 182261 7 74 95141 468079 8 51 17254 35435 3 85 232992 429217 5 21 322232 113709 8 94 290870 95148 3 39 436099 266272 6 18 155735 195464 5 57 425279 330426 9 87 458100 189664 4 7...
output:
101011001000100011010111100000000001100001000010001010000000010000101001100001101011000000000001011000000000010000100000101000001000001010111001100010111001100100101001010010101001110101001000011010110100000000000011000111000011100010101000011011101001010000000000000110001000111010000010010010010000...
result:
ok single line: '101011001000100011010111100000...1000011010000010000101011000100'
Test #11:
score: 0
Accepted
time: 323ms
memory: 175160kb
input:
1 500000 500000 500000 463657 271762 1554 33 268462 416602 752 57 232884 291386 934 86 156239 192958 988 45 456182 465291 748 92 293901 200213 1764 35 400287 114393 1883 21 66445 186455 1936 72 256226 412499 235 53 118804 2424 556 48 217585 398265 1246 25 407376 105528 1711 66 437274 219222 268 60 2...
output:
100000000011001001000000000010100001000000100000000000100000000000111000000000001001010001100000100010100100110010010001010100100000100001001011010000100000000001001000001000000010001001010000000100000100010000001100000000000110100011100011000000000001100101000010100001000000000100011000011011000001...
result:
ok single line: '100000000011001001000000000010...0010011000010010110000100000000'
Test #12:
score: 0
Accepted
time: 557ms
memory: 153512kb
input:
1 200000 500000 390113 167473 53087 7 40 127766 31485 3 77 122178 73725 4 280 165130 187689 8 22 160640 31022 5 54 49941 108757 8 254 51900 63848 2 273 198039 105397 1 65 93834 156249 3 37 75775 72556 2 34 180908 4310 4 2088433 151872 97064 9 2866315 67375 4359 10 52 586 177196 4 16 79615 91304 9 19...
output:
110011000100010111000011111100001111100011011111110010001101100100110000110100111101101110101110011001101001000001111010011111100001101001101110110101110000001010100010011001010110100010000001101000010011100111000101011000111001011111001011101000100101100001101001010011101100011011011110000010011011...
result:
ok single line: '110011000100010111000011111100...1101010101101100101011001110001'
Test #13:
score: 0
Accepted
time: 394ms
memory: 162540kb
input:
1 200000 500000 500000 61211 118103 144 81836 13561 22617 1166 402 173146 85997 505 163 32172 185229 1321 5 41738 20077 411 2855263 178084 192923 989 4 106963 88155 633 80 195732 105926 856 98 79684 164339 1574 14 17805 63626 1763 3746238 62051 33869 1417 315 94813 102630 125 57 117507 184986 633 18...
output:
110000110011001110011000101001000100100100000101010001100010001001100000100001000010100000000100001000100000100011010100010001001000000011001010100010000111000000000000110000110000001000010010011100000000000000001010001110010000000000000010100010100000000001110010011110000001001001000011000100101010...
result:
ok single line: '110000110011001110011000101001...0000001000110100110110100000000'
Test #14:
score: 0
Accepted
time: 522ms
memory: 177124kb
input:
1 500000 500000 500000 420052 355289 2 2 309678 317458 8 11 61704 8266 7 70 296113 396246 3 83 475788 162969 5 93 22424 181415 9 7 480390 28262 1 10 380549 78679 8 13 152190 61422 8 31 259056 208854 8 4 138165 249290 10 58 57100 212361 9 82 106575 201277 2 13 73829 439668 6 62 140443 219369 8 5 1078...
output:
100001101101011110010011011011101110111100011101010110110111010010011110110100111101010001001011111110100111001100011011011111111001101101010110111001110101100100111101011110111110111100000011001011100011111011111111111100110011110110100101000100001111111010100101111001001010101111000000011111011010...
result:
ok single line: '100001101101011110010011011011...1111101111110011101100111111111'
Test #15:
score: 0
Accepted
time: 341ms
memory: 175400kb
input:
1 500000 500000 500000 270234 117804 1782 59 487444 34087 1664 66 289462 489609 781 27 41700 352509 1870 14 218553 6119 572 97 215144 2258 1486 58 229758 75287 650 96 390152 474120 781 78 281060 391879 845 72 212023 73757 845 43 175436 194520 737 47 385899 101608 887 85 398726 250221 1429 62 67802 7...
output:
110100100100000100010100000000000110100101000000001000101010100000000010100011100000111010100001000001000011101100110101111001000010010111101001000010000011000000001100100000011001000010100100000101001011000000100101000101000010000001101100111100000000010000000010010010011001001100000000001110001001...
result:
ok single line: '110100100100000100010100000000...0100000000001010000000000000010'
Test #16:
score: 0
Accepted
time: 560ms
memory: 164384kb
input:
1 250002 500000 500000 1 2 1 115683844 2 250002 1 850281965 1 3 1 900000009 3 250002 1 854267056 1 4 1 444184972 4 250002 1 851353302 1 5 1 314211665 5 250002 1 863294696 1 6 1 900000009 6 250002 1 874026313 1 7 1 900000009 7 250002 1 840010136 1 8 1 496150051 8 250002 1 899450367 1 9 1 900000009 9 ...
output:
110110010000101110010111111100011010001000101110111110011111011000001111101110111111000010000011000111111101011001011011111111110110100010101000000000010100000101101001110000010100011011001100001110000101100000111000010000010101110101100001101111100110001111011000010110101110111111011000100001100110...
result:
ok single line: '110110010000101110010111111100...0110001100011010100010101011011'
Test #17:
score: -100
Time Limit Exceeded
input:
1 500000 499999 500000 1 2 1 900000001 2 3 1 889793906 2 4 1 866671124 2 5 1 845385183 2 6 1 851253005 2 7 1 810344594 2 8 1 891357151 2 9 1 880320997 2 10 1 838371291 2 11 1 835447460 2 12 1 863553591 2 13 1 856806584 2 14 1 856885463 2 15 1 852192684 2 16 1 891121453 2 17 1 811660786 2 18 1 879481...