QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#478717 | #996. 割点 | PYD1# | WA | 2ms | 5356kb | C++14 | 1.9kb | 2024-07-15 10:31:33 | 2024-07-15 10:31:34 |
Judging History
answer
#include <set>
#include <map>
#include <list>
#include <queue>
#include <cmath>
#include <time.h>
#include <random>
#include <bitset>
#include <vector>
#include <cstdio>
#include <stdio.h>
#include <iomanip>
#include <assert.h>
#include <stdlib.h>
#include <memory.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define mk make_pair
#define fi first
#define se second
char buf[1 << 20],*p1,*p2;
inline char gc(){
if (p1 == p2){
p1 = buf;
p2 = buf + fread(buf,1,1 << 20,stdin);
}
return p1 == p2 ? EOF : *p1++;
// return getchar();
}
inline int read(){
int t = 0,f = 1;
register char c = gc();
while (c < 48 || c > 57) f = (c == '-') ? (-1) : (f),c = gc();
while (c >= 48 && c <= 57) t = (t << 1) + (t << 3) + (c ^ 48),c = gc();
return f * t;
}
const int N = 2e4 + 3,M = 1e5 + 3;
int n,m,etot = 1,dfncnt,head[N],dfn[N],low[N];
struct Edge{
int u,v,nxt;
}e[M << 1];
inline void adde(int u,int v) {e[++etot] = (Edge){u,v,head[u]},head[u] = etot;}
vector <int> ans;
void Tarjan(int u,int f){
dfn[u] = low[u] = ++dfncnt;int child = 0;bool flag = 0;
for (int i = head[u];i;i = e[i].nxt){
int v = e[i].v;
if (v == f) continue;
if (!dfn[v]) Tarjan(v,i),low[u] = min(low[u],low[v]),++child;
else low[u] = min(low[u],dfn[v]);
if (low[v] >= dfn[u]) flag = 1;
}
if ((f && flag) || (!f && child > 1)) ans.emplace_back(u);
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.in","r",stdin);
// freopen("out.out","w",stdout);
#endif
n = read(),m = read();
for (int i = 1;i <= m;i++){
int u = read(),v = read();
adde(u,v),adde(v,u);
}
for (int i = 1;i <= n;i++) if (!dfn[i]) Tarjan(i,0);
sort(ans.begin(),ans.end());
printf("%d\n",(int)ans.size());
for (int p : ans) printf("%d ",p);puts("");
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 5356kb
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:
3073 10 13 22 26 27 29 31 32 33 34 35 37 39 44 45 47 49 50 53 55 61 62 63 66 67 78 84 91 94 99 105 106 110 118 121 126 127 132 133 138 144 145 146 151 155 156 163 166 168 174 176 177 178 179 183 186 187 188 192 194 196 199 200 202 205 208 210 212 214 215 219 220 223 225 226 234 239 244 247 248 250 2...
result:
wrong answer 1st numbers differ - expected: '1440', found: '3073'