QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #801678 | #8943. Challenge Matrix Multiplication | Infinite_Loopers# | WA | 326ms | 69408kb | C++20 | 1.7kb | 2024-12-07 05:23:36 | 2024-12-07 05:23:36 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
int n, m;
cin >> n >> m;
vector<vector<int>> adj(n);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
u--, v--;
adj[u].push_back(v);
}
vector<vector<int>> paths;
vector<vector<pair<int, int>>> path_pos(n);
vector<vector<int>> adj2 = adj;
for (int i = 0; i < n; i++) {
while (!empty(adj2[i])) {
vector<int> path;
int u = i;
path.push_back(u);
path_pos[u].emplace_back(ssize(paths), 0);
while (!empty(adj2[u])) {
int v = adj2[u].back();
adj2[u].pop_back();
u = v;
path_pos[u].emplace_back(ssize(paths), ssize(path));
path.push_back(u);
}
paths.push_back(move(path));
}
}
vector<vector<int>> counts(ssize(paths));
vector<int> infinity(ssize(paths));
for (int i = 0; i < ssize(paths); i++) {
auto &p = paths[i];
infinity[i] = ssize(p);
auto &c = counts[i];
c.resize(ssize(p) + 1);
for (int j = ssize(p)-1; j >= 0; j--) {
c[j] = c[j+1] + (path_pos[p[j]][0].first == i);
}
}
vector<vector<int>> dp(ssize(paths), infinity);
vector<int> ans(n, 1);
for (int i = n-1; i >= 0; i--) {
if (empty(path_pos[i])) continue;
vector<int> &d = dp[path_pos[i][0].first];
for (auto [p,j]: path_pos[i]) d[p] = min(d[p], j);
for (int v: adj[i]) {
auto [p,j] = path_pos[v][0];
auto &d2 = dp[p];
for (int j = 0; j < ssize(paths); j++) {
d[j] = min(d[j], d2[j]);
}
}
int r = 0;
for (int p = 0; p < ssize(paths); p++) r += counts[p][d[p]];
ans[i] = r;
}
for (int r: ans) {
cout << r << " ";
}
cout << "\n";
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3808kb
input:
4 6 1 3 2 3 2 4 1 2 1 3 1 3
output:
4 3 1 1
result:
ok 4 number(s): "4 3 1 1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3844kb
input:
5 7 1 4 1 5 1 2 2 4 3 4 2 5 1 4
output:
4 3 2 1 1
result:
ok 5 number(s): "4 3 2 1 1"
Test #3:
score: 0
Accepted
time: 1ms
memory: 3708kb
input:
100 900 89 90 34 35 45 46 97 98 41 42 59 61 19 20 25 29 2 3 28 29 54 55 77 78 69 74 60 61 43 44 13 14 92 93 65 66 68 69 72 73 78 81 54 56 55 60 14 15 9 10 92 93 10 11 18 19 16 17 97 98 76 77 39 40 71 72 7 8 63 64 7 8 16 24 13 24 83 84 90 91 1 4 4 5 96 97 81 82 91 92 80 81 66 67 19 20 3 4 9 10 47 48 ...
output:
100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
result:
ok 100 numbers
Test #4:
score: 0
Accepted
time: 1ms
memory: 3940kb
input:
100 900 71 72 22 26 21 22 15 22 97 98 43 44 64 65 87 88 79 81 90 93 54 55 96 97 64 67 64 88 24 25 71 72 47 48 49 51 72 75 12 14 66 67 6 7 90 91 14 15 73 74 99 100 66 73 84 85 34 35 94 95 88 89 16 17 17 20 56 57 13 14 13 14 48 51 80 81 7 9 26 27 42 44 86 87 31 36 82 83 54 55 7 8 20 21 41 42 17 18 91 ...
output:
100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
result:
ok 100 numbers
Test #5:
score: 0
Accepted
time: 1ms
memory: 3900kb
input:
100 916 93 97 2 3 77 78 47 50 23 24 25 31 31 32 59 61 69 74 8 9 4 5 30 31 73 74 3 4 12 15 36 37 80 84 44 47 84 85 9 18 78 79 74 76 45 46 89 96 76 78 20 21 22 24 35 36 20 22 36 37 25 26 82 83 40 42 95 96 29 30 92 93 93 94 21 22 34 35 65 66 32 33 71 72 9 11 87 88 69 71 12 13 46 47 3 4 3 4 59 62 64 65 ...
output:
100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
result:
ok 100 numbers
Test #6:
score: 0
Accepted
time: 1ms
memory: 3580kb
input:
100 843 62 64 78 80 10 11 31 37 37 48 64 66 24 25 77 79 68 69 10 11 76 78 89 90 37 41 20 21 42 43 30 36 47 48 66 68 10 11 18 21 59 62 30 31 42 49 56 66 78 83 37 39 65 67 96 97 24 73 26 28 21 22 82 83 94 96 39 40 8 10 89 90 51 52 92 93 85 87 34 62 6 7 97 98 13 14 5 6 29 30 7 10 41 42 70 71 21 23 48 5...
output:
100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
result:
ok 100 numbers
Test #7:
score: 0
Accepted
time: 1ms
memory: 3636kb
input:
100 910 74 75 90 91 66 67 84 85 56 57 86 87 29 30 92 93 30 53 91 92 55 58 43 44 58 59 65 66 75 76 46 47 50 51 99 100 57 58 37 39 75 77 35 36 2 3 39 41 70 71 85 86 4 5 56 57 28 29 67 69 98 99 3 4 80 81 9 12 9 10 79 80 68 70 3 4 72 73 81 82 54 55 97 98 7 8 94 97 69 70 56 57 69 71 6 7 49 50 26 27 80 81...
output:
100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
result:
ok 100 numbers
Test #8:
score: -100
Wrong Answer
time: 326ms
memory: 69408kb
input:
300000 1000000 291518 291525 162078 162095 107433 107434 117028 117029 252973 252975 34296 34301 17712 17713 168224 168227 5479 5480 96730 96733 18177 18182 170140 170142 114143 114145 290862 290865 239489 239490 132218 132219 143908 143914 118103 118105 76237 76240 265590 265591 42005 42010 95874 9...
output:
296803 296802 296801 296800 296799 296797 296796 296796 296795 1 296794 296793 296792 296791 296790 296789 296788 296787 296786 296785 296784 296782 296782 296781 296780 296779 296778 296777 296776 296775 296774 296773 296772 296771 296770 296768 296768 296767 296766 296765 296764 296763 296762 2967...
result:
wrong answer 34th numbers differ - expected: '296769', found: '296771'