QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#589910 | #996. 割点 | absabs | WA | 6ms | 10148kb | C++14 | 2.1kb | 2024-09-25 20:34:30 | 2024-09-25 20:34:31 |
Judging History
answer
// #pragma GCC optimize(2)
// #pragma GCC optimize(3,"Ofrrst","inline")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define ull unsigned long long
#define ll __int128_t
#define fre freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
mt19937 rd(chrono::system_clock::now().time_since_epoch().count());
const int mod=998244353;
const int inf=0x3f3f3f3f3f3f3f3f;
const int N=2e5+10;
const double eps=1e-6;
const int hash_p1=1610612741;
const int hash_p2=805306457;
const int hash_p3=402653189;
const int base_1=131;
const int base_2=13331;
int n,m;
#define pre(i,a,b) for(int i=a;i<=b;i++)
vector<int> g[N];
int dfn[N],low[N],deep,cut[N],cnt;
// v:当前点 r:本次搜索树的root
void tarjan(ll u, ll r) {
dfn[u] = low[u] = ++deep;
ll child = 0;
for (auto v : g[u]) {
if (!dfn[v]) {
tarjan(v, r);
low[u] = min(low[u], low[v]);
if (low[v] >= dfn[u] && u != r) cut[u] = 1,cnt ++;//不是根而且他的孩子无法跨越他回到祖先 割点
if (r == u)child++; //如果是搜索树的根,统计孩子数目
}
low[u] = min(low[u], dfn[v]);//已经搜索过了
}
if (child >= 2 && u == r)cut[r] = 1,cnt ++;
}
void solve()
{
cin >> n >> m;
for(int i=1;i<=m;i++)
{
int u,v;
cin >> u >> v;
g[u].push_back(v),g[v].push_back(u);
}
pre(i,1,n)
{
if(!dfn[i])
tarjan(i,i);
}
cout << cnt << endl;
pre(i,1,n)
{
if(cut[i]) cout << i << " ";
}
}
//#define LOCAL
signed main(){
ios
//fre
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
auto start = std::chrono::high_resolution_clock::now();
#endif
int _=1;
// cin>>_;
while(_--)solve();
#ifdef LOCAL
auto end = std::chrono::high_resolution_clock::now();
cout << "Execution time: "
<< std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count()
<< " ms" << '\n';
#endif
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 6ms
memory: 10148kb
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:
1545 13 22 26 27 29 33 35 37 39 45 47 53 62 78 91 118 127 132 144 151 155 156 163 166 168 177 183 187 192 194 196 205 219 220 223 225 239 248 250 254 256 265 285 290 313 315 337 338 347 356 358 376 386 388 408 414 415 427 446 459 461 464 477 486 504 513 519 538 555 557 571 574 608 611 619 625 626 63...
result:
wrong answer 1st numbers differ - expected: '1440', found: '1545'