QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#329619#6152. 骑士游戏DGME20 0ms16228kbC++231.3kb2024-02-16 23:09:192024-02-16 23:09:19

Judging History

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

  • [2024-02-16 23:09:19]
  • 评测
  • 测评结果:20
  • 用时:0ms
  • 内存:16228kb
  • [2024-02-16 23:09:19]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int64_t, int>;
constexpr int N = 2e5 + 10;
vector<int> adj[N];
__int128_t dis[N], Z[N];
map<int, int> sp[N];
signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    int n;cin >> n;
    for (int i = 1;i <= n;i ++ ) {
        int s, k, r;
        cin >> s >> k >> r;
        dis[i] = k, Z[i] = s;
        
        while (r -- ) {
            int a;cin >> a;
            adj[a].push_back(i);
        }
    }

    for (int i = 1;i <= n;i ++ ) {
        for (auto x : adj[i]) sp[x][i] ++;
        sort(adj[i].begin(), adj[i].end());
        adj[i].erase(unique(adj[i].begin(), adj[i].end()), adj[i].end());
    }
    vector<int> deg(n + 1);
    for (int i = 1;i <= n;i ++ ) 
        deg[i] = sp[i].size();

    vector<bool> vis(n + 1);
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    for (int i = 1;i <= n;i ++ ) {
        pq.push({dis[i], i});
    }
    while (pq.size()) {
        auto [d, u] = pq.top();pq.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (auto x : adj[u]) {
            Z[x] += dis[u] * sp[x][u];
            if (-- deg[x] == 0) {
                int64_t sum = 0;
                dis[x] = min(dis[x], Z[x]);
                pq.push({dis[x], x});
            }
        }
    }
    cout << (int64_t)dis[1] << '\n';
}

詳細信息

Test #1:

score: 10
Accepted
time: 0ms
memory: 16228kb

input:

5
25 30939 18 2 5 3 2 2 3 5 4 5 4 5 2 4 3 5 2 4 3
1 5194 18 3 4 5 4 4 4 3 4 5 4 5 5 3 5 4 4 5 4
3 988 6 4 5 4 5 4 4
15 236 8 5 5 5 5 5 5 5 5
11 27 30 1 4 4 2 4 1 1 3 3 2 3 1 1 4 3 1 4 2 1 4 2 2 3 3 1 3 4 1 4 2

output:

30933

result:

ok 1 number(s): "30933"

Test #2:

score: 10
Accepted
time: 0ms
memory: 15448kb

input:

5
10 855839 41 2 4 3 4 2 2 5 4 3 4 4 2 3 5 4 4 2 2 2 3 3 2 2 3 2 3 2 4 4 5 2 3 3 3 3 2 2 4 4 5 2
31 51271 28 3 5 4 5 4 4 4 5 4 5 4 3 4 4 3 5 4 4 5 4 5 3 4 3 4 4 5 3
33 7631 25 5 4 5 4 4 5 4 5 5 5 4 5 4 5 4 4 4 4 5 5 5 4 4 4 5
6 86 50 3 2 3 3 3 3 1 5 1 1 2 1 3 1 1 1 1 1 3 3 5 1 2 3 5 1 2 3 1 2 2 2 1 ...

output:

855836

result:

ok 1 number(s): "855836"

Test #3:

score: 0
Time Limit Exceeded

input:

300
664 10608068091 21 179 13 32 230 84 205 288 36 55 160 78 81 207 68 105 150 267 252 270 233 151
469 30572 4 43 39 65 190
598 1606767 14 193 249 105 138 262 150 217 291 16 248 99 273 300 51
717 98557 9 202 267 85 267 148 270 16 244 200
379 5691 1 260
888 345011781 13 126 225 286 221 197 76 292 76 ...

output:


result:


Test #4:

score: 0
Time Limit Exceeded

input:

300
362 2627659830 19 37 214 121 243 262 191 7 204 241 269 297 183 255 38 17 294 82 259 118
960 14600 3 215 13 125
933 1566 1 278
108 26020 4 138 215 178 23
66 407 45 230 194 52 133 15 274 142 259 153 107 250 2 183 20 242 221 192 195 7 290 12 213 163 274 114 159 154 77 62 32 107 6 107 211 43 148 259...

output:


result:


Test #5:

score: 0
Runtime Error

input:

300
95 91999352959 27 244 268 166 274 125 288 204 74 298 218 124 91 14 149 216 140 15 238 115 202 47 252 69 152 215 63 265
85 4445 6 265 258 57 159 89 80
65 130135 6 76 82 25 2 23 195
44 433190084 16 24 237 67 20 224 27 127 256 113 248 146 111 15 102 56 68
24 68146993 21 109 178 291 175 3 223 238 95...

output:


result:


Test #6:

score: 0
Time Limit Exceeded

input:

100000
24 227132235858504 21 89069 36420 56272 95210 88994 70315 79864 2217 3058 31935 63821 81062 92637 40534 83476 38445 43474 79687 25738 81533 76567
42 114 2 64023 461
27 4012 5 74206 42155 86316 66837 28480
44 3648 5 34056 29352 49996 37219 62936
13 74 2 62885 26204
6 27202 9 37211 7379 31135 8...

output:


result:


Test #7:

score: 0
Runtime Error

input:

100000
23 475912433278938 21 79558 92527 94745 76117 98709 13530 90434 39328 26160 39374 96375 42888 96582 2391 56133 68240 91718 3575 60043 69944 80435
11 56584 4 65507 9017 41623 7306
1 103 2 41737 81685
18 1141 3 68539 51072 14552
22 91 1 51850
29 48131 11 55898 27553 53310 74224 63797 28150 1493...

output:


result:


Test #8:

score: 0
Runtime Error

input:

200000
8 2639675578598 8 155168 113497 194918 184419 104869 103169 81289 71670
15 2542 8 41217 53912 156767 21575 107897 196366 138171 16831
15 741 1 1910
20 203 2 85038 115654
6 224 3 49196 160690 164392
39 829 5 78516 138433 126489 154519 92637
18 80 2 54837 59653
6 1072 4 92536 87141 76281 56303
...

output:


result:


Test #9:

score: 0
Time Limit Exceeded

input:

200000
23 44515460034753 3 175400 194705 6078
50 171 3 121618 167218 131398
12 121 2 94037 154080
45 6593 6 1019 603 94945 123093 60760 28124
10 310 2 109715 44476
50 1531 4 31355 180851 66292 58474
2 626 3 115557 31001 115583
14 654 1 112608
46 1035 4 154554 67739 139667 61584
5 3903 4 33292 58161 ...

output:


result:


Test #10:

score: 0
Time Limit Exceeded

input:

200000
18 351509962255574 6 173868 191437 136350 158949 44658 126779
14 802 5 157965 189081 94896 104023 153438
40 4559 5 44892 23316 95269 58595 55141
18 396 3 116395 144029 95596
14 1043 1 71
14 25 1 177224
28 1378 4 90416 135893 131299 77741
39 2827 7 22617 100838 93683 49225 56714 107096 175420
...

output:


result: