Submission #1257677

#TimeUsernameProblemLanguageResultExecution timeMemory
1257677Zbyszek99Potemkin cycle (CEOI15_indcyc)C++20
100 / 100
207 ms114908 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define ll long long #define ld long double #define ull unsigned long long #define ff first #define ss second #define pii pair<int,int> #define pll pair<long long, long long> #define vi vector<int> #define vl vector<long long> #define pb push_back #define rep(i, b) for(int i = 0; i < (b); ++i) #define rep2(i,a,b) for(int i = a; i <= (b); ++i) #define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c) #define count_bits(x) __builtin_popcountll((x)) #define all(x) (x).begin(),(x).end() #define siz(x) (int)(x).size() #define forall(it,x) for(auto& it:(x)) using namespace __gnu_pbds; using namespace std; typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set; //mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());} //ll los(ll a, ll b) {return a + (mt() % (b-a+1));} const int INF = 1e9+50; const ll INF_L = 1e18+40; const ll MOD = 1e9+7; int edge[1001][1001]; vi graph[1001]; vi graph2[1003001]; int color[1003001]; vi cycle; vi path; bool in_cycle[1001]; void dfs(int v) { color[v] = 1; path.pb(v); forall(it,graph2[v]) { if(color[it] == 0) { dfs(it); if(siz(cycle) != 0) return; } else if(color[it] == 1) { while(path.back() != it) { cycle.pb(path.back()); path.pop_back(); } cycle.pb(it); reverse(all(cycle)); return; } } path.pop_back(); color[v] = 2; } int main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); //random_start(); int n,m; cin >> n >> m; rep(i,m) { int a,b; cin >> a >> b; if(a == b) continue; edge[a][b] = 1; edge[b][a] = 1; graph[a].pb(b); graph[b].pb(a); } rep2(i,1,n) { forall(it,graph[i]) { forall(it2,graph[i]) { if(edge[it2][it] == 0 && it != it2) { int p1 = it+i*(n+1); int p2 = i+it2*(n+1); graph2[p1].pb(p2); } } } } rep(i,n*(n+2)) { if(color[i] == 0 && siz(cycle) == 0) { dfs(i); } } if(siz(cycle) == 0) cout << "no\n"; vi c; forall(it,cycle) { c.pb(it%(n+1)); } cycle = c; rep(i,siz(c)) { int it = c[i]; in_cycle[it] = 1; forall(it2,graph[it]) { if(in_cycle[it2] && i != 0 && it2 != c[i-1]) { vi ans; for(int j = i; j >= 0; j--) { ans.pb(c[j]); if(c[j] == it2) break; } forall(it,ans) cout << it << " "; return 0; } } } forall(it,c) cout << it << " "; }
#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...