QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#719169#9431. The Quest for El DoradoQSteve_PaulTL 630ms177124kbC++234.5kb2024-11-06 23:01:082024-11-06 23:01:09

Judging History

你现在查看的是最新测评结果

  • [2024-11-06 23:01:09]
  • 评测
  • 测评结果:TL
  • 用时:630ms
  • 内存:177124kb
  • [2024-11-06 23:01:08]
  • 提交

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...

output:


result: