QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#534202 | #121. Bitaro's Party | isirazeev | 0 | 180ms | 86500kb | C++20 | 2.2kb | 2024-08-26 21:56:40 | 2024-08-26 21:56:40 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = (int) 1e5 + 10;
const int C = 1300;
const int INF = (int) 1e18;
set<pair<int, int>> biggest[N];
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int n, m, q;
cin >> n >> m >> q;
vector<int> rev_g[n];
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
rev_g[v - 1].emplace_back(u - 1);
}
for (int i = 0; i < n; i++) {
biggest[i].insert({0, i});
set<int> was;
map<int, int> dist;
dist[i] = 0;
was.insert(i);
for (int j: rev_g[i]) {
for (auto [c, ind]: biggest[j]) {
if (was.find(ind) != was.end()) {
if (dist[ind] < c + 1) {
biggest[i].erase({dist[ind], ind});
dist[ind] = c + 1;
biggest[i].insert({c + 1, ind});
}
} else {
biggest[i].insert({c + 1, ind});
}
if ((int) biggest[i].size() > C) biggest[i].erase(biggest[i].begin());
}
}
}
for (int _ = 0; _ < q; _++) {
int T, Y;
cin >> T >> Y;
T--;
set<int> block;
for (int i = 0; i < Y; i++) {
int A;
cin >> A;
block.insert(A - 1);
}
if (Y >= C) {
int dp[n];
for (int i = 0; i < n; i++) dp[i] = -INF;
dp[T] = 0;
for (int i = T; i >= 0; i--) {
for (int j: rev_g[i])
dp[j] = max(dp[j], dp[i] + 1);
}
int res = -1;
for (int i = 0; i < n; i++) if (block.find(i) == block.end()) res = max(res, dp[i]);
cout << res << "\n";
continue;
} else {
int res = -1;
for (auto [val, ind]: biggest[T]) {
if (block.find(ind) == block.end())
res = max(res, val);
}
cout << res << "\n";
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 7
Accepted
time: 2ms
memory: 8472kb
input:
1 0 1 1 0
output:
0
result:
ok single line: '0'
Test #2:
score: 7
Accepted
time: 2ms
memory: 8176kb
input:
1 0 1 1 1 1
output:
-1
result:
ok single line: '-1'
Test #3:
score: 7
Accepted
time: 0ms
memory: 8436kb
input:
2 1 1 1 2 1 2 1 2
output:
-1
result:
ok single line: '-1'
Test #4:
score: 7
Accepted
time: 2ms
memory: 8500kb
input:
2 1 1 1 2 1 1 1
output:
-1
result:
ok single line: '-1'
Test #5:
score: 7
Accepted
time: 18ms
memory: 16020kb
input:
1000 2000 1 66 427 211 505 213 674 56 131 180 883 127 167 228 262 42 50 386 688 346 943 170 396 127 150 169 192 253 706 96 497 141 277 317 711 792 802 244 469 24 702 135 252 31 764 52 95 701 900 473 832 510 691 14 474 158 488 422 491 228 897 318 622 195 548 479 626 525 728 53 109 133 854 392 416 34 ...
output:
12
result:
ok single line: '12'
Test #6:
score: 7
Accepted
time: 13ms
memory: 14716kb
input:
1000 2000 1 762 826 799 904 17 20 56 733 46 416 261 768 196 392 121 144 14 69 244 625 331 485 331 383 502 635 107 914 131 274 288 495 70 103 417 934 318 535 775 930 9 113 250 677 82 200 2 4 36 77 367 553 8 31 633 712 21 179 484 963 117 146 207 413 685 787 561 903 508 710 834 912 4 76 196 977 355 394...
output:
14
result:
ok single line: '14'
Test #7:
score: 7
Accepted
time: 17ms
memory: 14944kb
input:
1000 2000 1 86 222 107 710 207 983 80 929 4 5 685 963 758 769 228 274 34 35 14 26 614 786 383 679 41 62 125 522 619 851 175 359 253 492 127 182 27 367 111 221 170 453 519 612 137 191 254 301 53 148 214 824 31 374 402 795 25 26 177 461 301 614 574 798 82 104 137 625 86 575 32 364 37 183 131 270 113 6...
output:
2
result:
ok single line: '2'
Test #8:
score: 7
Accepted
time: 178ms
memory: 86500kb
input:
1000 2000 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52...
output:
181
result:
ok single line: '181'
Test #9:
score: 7
Accepted
time: 173ms
memory: 86180kb
input:
1000 2000 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52...
output:
627
result:
ok single line: '627'
Test #10:
score: 0
Wrong Answer
time: 180ms
memory: 86100kb
input:
1000 2000 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52...
output:
-1
result:
wrong answer 1st lines differ - expected: '72', found: '-1'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%