Submission #204526

#	Time	Username	Problem	Language	Result	Execution time	Memory
204526		junodeveloper	Potemkin cycle (CEOI15_indcyc)	C++14	40 / 100	1121 ms	535868 KiB

indcyc

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define fi first
#define se second
#define mset(x,y) memset(x,y,sizeof(x))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repr(i,a,b) for(int i=(a);i>=(b);i--)
#ifdef LOCAL
#define debug(...) printf(__VA_ARGS__)
#else
#define debug(...) 1
#endif
using namespace __gnu_pbds;
using namespace std;
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
int n,m;
int grp[1010],gc,ver[1010],vc;
int cnt[1010];
bool chk[1010];
set<int> adj[1010];
void dfs(int u) {
	grp[u]=gc;
	ver[u]=vc;
	for(auto& it:adj[u])if(ver[it]!=vc&&!(chk[u]&&chk[it]))dfs(it);
}
void go(int a,int b) {
	vector<int> d(n+1,-1),par(n+1);
	queue<int> q;
	d[b]=0;q.push(b);
	while(!q.empty()) {
		int u=q.front();q.pop();
		if(chk[u]&&u!=b)continue;
		for(auto& it:adj[u]) {
			if(d[it]!=-1||ver[it]!=vc||(chk[u]&&chk[it]))continue;
			d[it]=d[u]+1;
			par[it]=u;
			q.push(it);
		}
	}
	for(auto& it:adj[b]) {
		if(!chk[it])continue;
		d[it]=0;
	}
	int e=-1;
	for(auto& it:adj[a]) if(d[it]>0) e=it;
	vi ans;
	while(e!=b){
		//assert(e!=-1);
		ans.pb(e),e=par[e];
	}
	ans.pb(b);ans.pb(a);
	for(auto& it:ans)printf("%d ",it);
}
namespace FIO {
	using ll=long long;
	int _curr, _size;
	char _buff[1<<20];
	char rc() {
		if(_curr == _size) {
			_size = (int)fread(_buff, 1, sizeof(_buff), stdin);
			_curr = 0;
		}
		if(!_size) return 0;
		return _buff[_curr++];
	}
	ll ri() {
		ll c, x = 0, f = 1;
		while((c = rc()) <= 32);
		if(c == '-') f = -1, c = rc();
		while(c > 32) x = (x << 3) + (x << 1) + c - 48, c = rc();
		return x * f;
	}
}
using namespace FIO;
int main() {
	int i,j,u,v;
	//scanf("%d%d",&n,&m);
	n=ri(),m=ri();
	for(i=1;i<=m;i++) {
		u=ri(),v=ri();
		//scanf("%d%d",&u,&v);
		adj[u].insert(v);
		adj[v].insert(u);
	}
	for(i=1;i<=n;i++) {
		chk[i]=true;vc=i;
		for(auto& it:adj[i])chk[it]=true;
		for(auto& it:adj[i])if(ver[it]!=vc) {
			gc++;
			dfs(it);
			cnt[gc]=0;
		}
		for(auto& it:adj[i])cnt[grp[it]]++;
		for(auto& it:adj[i]){
			j=0;
			for(auto& jt:adj[it]) {
				if(chk[jt]&&grp[it]==grp[jt])j++;
			}
			if(j!=cnt[grp[it]]-1) {
				go(i,it);
				return 0;
			}
		}
		chk[i]=false;
		for(auto& it:adj[i]) {
			chk[it]=false;
			adj[it].erase(i);
		}
	}
	puts("no");
	return 0;
}

Compilation message (stderr)

indcyc.cpp:2:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("O3")
 
indcyc.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10