제출 #1115946

#제출 시각아이디문제언어결과실행 시간메모리
1115946vjudge1Potemkin cycle (CEOI15_indcyc)C++17
20 / 100
13 ms7504 KiB
//Dost SEFEROĞLU #include <bits/stdc++.h> #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt") #pragma GCC optimize("O3,unroll-loops") using namespace std; #define int long long #define pii pair<int,int> #define ff first #define ss second #define sp << " " << #define all(cont) cont.begin(),cont.end() #define vi vector<int> int MOD = 998244353,inf = 2e18; const int N = 1e5+50,Q = 2e5+50; vi edges[N]; int tin[N],dep[N],par[N]; pii ans{-1,-1}; int timer = 1; bool anc(int a,int b) { if (b == -1) return 0; return tin[a] <= tin[b]; } void dfs(int node,int p,int der = 0,int ban = -1) { par[node] = p; dep[node] = der; tin[node] = timer++; pii maxdepshi = {-1,-1}; int banny = ban; for (auto it : edges[node]) { if (it == p) continue; if (tin[it] && (ban == -1 || tin[it] > tin[ban])) { ban = it; } if (tin[it] && dep[it] < dep[node]) maxdepshi = max(maxdepshi,{dep[it],it}); } if (maxdepshi.ff != -1 && dep[node]-maxdepshi.ff >= 3 && !anc(maxdepshi.ss,banny)) { ans = {node,maxdepshi.ss}; } for (auto it : edges[node]) { if (it == p) continue; else if (!tin[it]) dfs(it,node,der+1,ban); else if (dep[it] < dep[node]) maxdepshi = max(maxdepshi,{dep[it],it}); } } void solve() { int n,m; cin >> n >> m; for (int i=1;i<=m;i++) { int a,b; cin >> a >> b; edges[a].push_back(b); edges[b].push_back(a); } dfs(1,1); if (ans.ff == -1) { cout << "no\n"; return; } vi v; int cur = ans.ff; while (cur != ans.ss) { cout << cur << " "; cur = par[cur]; } cout << ans.ss << " "; cout << '\n'; } int32_t main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #ifdef Dodi freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif int t = 1; //cin >> t; while (t --> 0) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...