QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#329619 | #6152. 骑士游戏 | DGME | 20 | 0ms | 16228kb | C++23 | 1.3kb | 2024-02-16 23:09:19 | 2024-02-16 23:09:19 |
Judging History
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 ...