QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #587589 | #8943. Challenge Matrix Multiplication | A_programmer | RE | 16ms | 60712kb | C++17 | 1.5kb | 2024-09-24 20:44:40 | 2024-09-24 20:44:41 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 5;
vector<int> g[maxn], h[maxn], vec[65];
int in[maxn], q[maxn], hd, tl, cnt;
int bel[maxn], dis[maxn], n;
bool vis[maxn];
ll ans[maxn];
void Topo()
{
hd = 1, tl = 0;
for (int i = 1; i <= n; i++)
if (!in[i]) q[++tl] = i, vec[++cnt].emplace_back(i), bel[i] = cnt;
while (hd <= tl)
{
int u = q[hd++];
for (int v : g[u])
if (--in[v] == 0) q[++tl] = v;
bool Fl = 0;
for (int v : h[u]) vis[v] = 1;
for (int i = 1; i <= cnt; i++)
if (vis[vec[i].back()]) vec[i].emplace_back(u), bel[u] = i, Fl = 1;
if (!Fl) vec[++cnt].emplace_back(u), bel[u] = cnt;
assert(cnt <= 60);
for (int v : h[u]) vis[v] = 0;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int m;
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int u, v;
cin >> u >> v;
g[u].emplace_back(v);
in[v]++; h[v].emplace_back(u);
}
Topo();
for (int i = 1; i <= cnt; i++)
{
int nw = 0;
for (int j = 1; j <= n; j++) dis[j] = 0;
for (int j = vec[i].size(); j; j--)
{
nw += (bel[vec[i][j - 1]] == i);
dis[vec[i][j - 1]] = nw;
}
for (int j = n; j; j--)
{
int u = q[j];
for (int v : g[u]) dis[u] = max(dis[u], dis[v]);
ans[u] += dis[u];
}
}
for (int i = 1; i <= n; i++) cout << ans[i] << " ";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 16ms
memory: 58988kb
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: 3ms
memory: 59312kb
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: 8ms
memory: 59524kb
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: 4ms
memory: 60712kb
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: 7ms
memory: 60044kb
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: 3ms
memory: 60384kb
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: 4ms
memory: 58692kb
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
Runtime Error
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...