QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#671025 | #996. 割点 | dieselhuang | WA | 4ms | 8600kb | C++14 | 1003b | 2024-10-24 10:06:12 | 2024-10-24 10:06:13 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, dfx = 0, cnt = 0, hd[100010], e[1000010][2], dfn[100010], low[100010], ans[100010];
void dfs(int u, int fa){
dfn[u] = ++dfx; low[u] = u;
int i, v, x = 0;
bool fl = false;
for(i = hd[u]; i > 0; i = e[i][0]){
v = e[i][1];
if(dfn[v] == 0){
dfs(v, u);
x++;
low[u] = min(low[u], low[v]);
if(fa != 0 && low[v] >= dfn[u]) fl = true;
}else if(v != fa) low[u] = min(low[u], dfn[v]);
}
if(fl) ans[++cnt] = u;
if(fa == 0 && x > 1) ans[++cnt] = u;
}
int main()
{
int i, u, v;
scanf("%d%d", &n, &m);
for(i = 1; i <= n; i++) hd[i] = 0, dfn[i] = 0;
for(i = 2; i >> 1 <= m; i++){
scanf("%d%d", &u, &v);
e[i][0] = hd[u]; e[i][1] = v; hd[u] = i;
i++;
e[i][0] = hd[v]; e[i][1] = u; hd[v] = i;
}
for(i = 1; i <= n; i++){
if(dfn[i] == 0) dfs(i, 0);
}
sort(ans + 1, ans + cnt + 1);
printf("%d\n", cnt);
for(i = 1; i <= cnt; i++) printf("%d ", ans[i]);
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 4ms
memory: 8600kb
input:
12783 21968 4933 7832 8238 2739 3628 7841 9169 6390 7850 8797 8120 8710 5306 9807 10166 2063 2666 5157 5015 4651 4790 12586 10366 7137 12440 7218 6330 3670 2735 8492 1968 2750 6237 1112 6578 9221 743 3820 7155 4583 2537 9747 11331 9916 4454 5631 2978 10340 5293 1803 4944 4296 11800 2742 7903 2018 10...
output:
722 13 22 27 35 39 45 47 62 78 144 155 163 166 168 183 192 219 239 248 250 254 285 290 313 347 356 358 376 386 388 408 415 427 446 459 464 477 504 519 538 555 611 619 625 626 639 644 691 694 709 723 731 779 792 798 802 810 858 871 872 881 908 930 933 938 956 964 974 975 984 988 1012 1033 1043 1055 1...
result:
wrong answer 1st numbers differ - expected: '1440', found: '722'