QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #775142 | #2683. British Menu | zjc5 | WA | 3ms | 26116kb | C++14 | 2.4kb | 2024-11-23 14:52:51 | 2024-11-23 14:52:53 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N = 100010, M = 6;
int n, m, a[N], b[N], dfn[N], low[N], cnt;
int st[N], tp, fa[N], ta[N], ct[N], dis[N][M][M], cntt[N];
int in[N], f[N][M], ans;
bool ins[N], bl[M];
vector<int>v[N];
struct node {
int t, b;
};
vector<node>tar[N][M];
queue<int>q;
void tarjan(int x) {
dfn[x] = low[x] = ++cnt;
st[++tp] = x;
ins[x] = 1;
for (int t : v[x]) {
if (!dfn[t]) {
tarjan(t);
low[x] = min(low[x], low[t]);
} else if (ins[t])
low[x] = min(low[x], dfn[t]);
}
if (low[x] == dfn[x]) {
int y;
while (1) {
y = st[tp--];
fa[y] = x;
ins[y] = 0;
ta[y] = ++ct[x];
if (y == x) break;
}
}
}
void dfs(int st, int now, int d, int bel) {
for (int t : v[now])
if (fa[t] == bel && !bl[ta[t]]) {
dis[bel][st][ta[t]] = max(dis[bel][st][ta[t]], d + 1);
cntt[ta[t]]++;
if (cntt[ta[t]] <= 16) {
bl[ta[t]] = 1;
dfs(st, t, d + 1, bel);
bl[ta[t]] = 0;
}
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
cin >> a[i] >> b[i];
v[a[i]].push_back(b[i]);
}
for (int i = 1; i <= n; i++)
if (!dfn[i]) tarjan(i);
for (int i = 1; i <= n; i++) {
dis[fa[i]][ta[i]][ta[i]] = 0;
// cout << i << ":\n";
bl[ta[i]] = 1;
dfs(ta[i], i, 0, fa[i]);
bl[ta[i]] = 0;
}
// for (int i = 2; i <= 6; i++)
// for (int j = 2; j <= 6; j++)
// cout << i << "->" << j << ": " << dis[fa[i]][ta[i]][ta[j]] << "\n";
// for (int i = 1; i <= n; i++)
// cout << fa[i] << " ";
// puts("");
for (int i = 1; i <= m; i++) {
int p = fa[a[i]], q = fa[b[i]];
if (p != q) {
tar[p][ta[a[i]]].push_back({q, ta[b[i]]});
in[q]++;
}
}
for (int i = 1; i <= n; i++)
if (ct[i] && !in[i]) {
for (int j = 1; j <= ct[i]; j++) {
for (int k = 1; k <= ct[i]; k++)
f[i][j] = max(f[i][j], dis[i][k][j] + 1);
// if (i == 1) {
// cout << j << ":" << f[i][j] << "\n";
// }
}
q.push(i);
}
while (!q.empty()) {
int d = q.front();
q.pop();
for (int j = 1; j <= ct[d]; j++) {
int s = f[d][j] + 1;
for (node k : tar[d][j]) {
for (int p = 1; p <= ct[k.t]; p++)
f[k.t][p] = max(f[k.t][p], dis[k.t][k.b][p] + s);
in[k.t]--;
if (!in[k.t]) q.push(k.t);
}
}
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= ct[i]; j++)
ans = max(ans, f[i][j]);
cout << ans;
return 0;
}
/*
7 9
1 2
2 3
3 4
4 5
5 6
6 2
4 7
6 4
3 5
ans:7
*/
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 25628kb
input:
10 6 7 8 4 2 8 6 5 1 4 1 4 5
output:
3
result:
ok single line: '3'
Test #2:
score: 0
Accepted
time: 3ms
memory: 25960kb
input:
10 10 1 3 8 9 6 10 1 2 7 9 10 9 5 1 2 5 8 6 7 8
output:
5
result:
ok single line: '5'
Test #3:
score: 0
Accepted
time: 2ms
memory: 23260kb
input:
10 8 7 6 4 2 10 6 4 5 2 4 3 2 6 10 2 1
output:
4
result:
ok single line: '4'
Test #4:
score: 0
Accepted
time: 3ms
memory: 25680kb
input:
10 19 3 6 9 10 7 9 9 8 8 7 5 6 3 8 6 9 5 9 2 6 6 8 1 4 6 7 6 10 3 9 10 7 4 9 10 8 1 8
output:
6
result:
ok single line: '6'
Test #5:
score: 0
Accepted
time: 0ms
memory: 26116kb
input:
10 19 2 7 8 10 9 8 3 10 8 9 4 5 2 10 1 8 9 6 1 9 4 6 3 2 5 9 5 2 10 7 5 10 7 6 6 9 4 7
output:
8
result:
ok single line: '8'
Test #6:
score: 0
Accepted
time: 0ms
memory: 22464kb
input:
10 18 3 6 2 10 2 5 5 3 4 2 1 5 7 9 10 7 8 6 3 2 4 8 8 9 3 7 7 8 1 4 3 1 5 1 3 9
output:
9
result:
ok single line: '9'
Test #7:
score: 0
Accepted
time: 0ms
memory: 25784kb
input:
12 11 11 10 12 10 8 12 9 12 5 7 1 6 8 11 9 11 7 9 7 11 2 9
output:
5
result:
ok single line: '5'
Test #8:
score: 0
Accepted
time: 2ms
memory: 22944kb
input:
7 7 1 2 2 3 3 4 4 5 5 6 6 2 4 7
output:
6
result:
ok single line: '6'
Test #9:
score: 0
Accepted
time: 0ms
memory: 25684kb
input:
9 9 1 2 2 3 3 4 4 5 5 6 6 2 4 7 8 1 9 8
output:
8
result:
ok single line: '8'
Test #10:
score: 0
Accepted
time: 0ms
memory: 25728kb
input:
7 9 1 2 2 3 3 4 4 5 5 6 6 2 4 7 6 4 3 5
output:
7
result:
ok single line: '7'
Test #11:
score: 0
Accepted
time: 2ms
memory: 23352kb
input:
9 9 1 2 2 3 3 4 4 5 5 6 6 4 4 7 7 8 8 9
output:
7
result:
ok single line: '7'
Test #12:
score: -100
Wrong Answer
time: 0ms
memory: 22368kb
input:
100 600 1 81 1 48 1 64 1 74 1 30 1 58 1 53 1 46 1 76 1 66 1 51 1 68 1 99 1 71 1 41 1 44 1 47 1 19 3 54 4 83 4 33 4 63 4 83 4 29 5 18 5 80 5 49 5 60 5 11 5 78 5 62 5 89 5 45 6 40 6 50 6 21 6 52 6 97 6 49 6 98 6 5 6 43 6 46 6 2 6 19 6 81 7 92 7 34 7 97 7 63 7 2 8 97 9 87 9 3 9 2 10 3 10 90 12 37 12 88...
output:
64
result:
wrong answer 1st lines differ - expected: '90', found: '64'