QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#129087#996. 割点Terdy#WA 1ms8308kbC++141.2kb2023-07-21 21:02:422023-07-21 21:02:43

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-21 21:02:43]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:8308kb
  • [2023-07-21 21:02:42]
  • 提交

answer

# include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;
int n , m;
int ecnt = 1 , head[N] , to[N] , nxt[N];
int ans , rt , DFN[N] , LOW[N] , Tcnt , cut[N];

void AddEdge(int u , int v) {nxt[++ecnt] = head[u] , head[u] = ecnt , to[ecnt] = v;}

void tarjan(int u , int fa)
{
    int cnt = 0;
    DFN[u] = LOW[u] = ++Tcnt;
    for(int i = head[u]; i; i = nxt[i])
    {
        int v = to[i];
        if(!DFN[v])
        {
            cnt++;
            tarjan(v , u);
            LOW[u] = min(LOW[u] , LOW[v]);
            if(u != rt && LOW[v] >= DFN[u]) cut[u] = 1;
        }
        LOW[u] = min(LOW[u] , LOW[v]);
    }
    // cout << u << ' ' << rt << ' ' << cnt << endl;
    if(!fa && cnt > 1) cut[u] = 1;
}

void Tarjan()
{
    for(int i = 1; i <= n; i++) if(!DFN[i])
        rt = i , tarjan(i , 0);
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for(int i = 1 , u , v; i <= m; i++) cin >> u >> v , AddEdge(u , v) , AddEdge(v , u);
    Tarjan();
    for(int i = 1; i <= n; i++) if(cut[i]) ans++;
    cout << ans << endl;
    for(int i = 1; i <= n; i++) if(cut[i]) cout << i << endl;
    return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 8308kb

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:

420
29
33
91
144
151
155
166
187
192
219
223
239
250
256
265
315
338
347
388
414
459
538
574
653
728
752
858
871
872
930
938
959
964
988
1010
1015
1046
1068
1084
1124
1180
1186
1235
1293
1319
1395
1459
1511
1544
1558
1568
1577
1603
1646
1693
1880
1927
1948
1953
1955
1978
2018
2033
2097
2161
2184
219...

result:

wrong answer 1st numbers differ - expected: '1440', found: '420'