Submission #205615

#	Time	Username	Problem	Language	Result	Execution time	Memory
205615		junodeveloper	Potemkin cycle (CEOI15_indcyc)	C++14	90 / 100	803 ms	11384 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,vis[1010],vc,st,f1,f2;
int cnt[1010];
bool chk[1010];
set<int> adj[1010];
bool am[1010][1010];
vi v;
void dfs(int u) {
	if(f1) return;
	vis[u]=vc;
	debug("u:%d\n",u);
	if(chk[u]) {
		debug("**u:%d\n",u);
		for(auto& it:v) {
			if(!am[it][u]) {
				f1=u,f2=it;
			}
		}
		v.pb(u);
		return;
	}
	for(auto& it:adj[u])if(!vis[it])dfs(it);
}
void go(int a,int b,int c) {
	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||(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;
	}
	vi ans;
	while(c!=b){
		assert(c!=-1);
		ans.pb(c),c=par[c];
	}
	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;
	//scanf("%d%d",&n,&m);
	n=ri(),m=ri();
	for(i=1;i<=m;i++) {
		int u=ri(),v=ri();
		//scanf("%d%d",&u,&v);
		adj[u].insert(v);
		adj[v].insert(u);
		am[u][v]=am[v][u]=true;
	}
	for(i=1;i<=n;i++) {
		chk[i]=true;
		for(auto& it:adj[i])chk[it]=true;
		mset(vis,0);vc=0;
		debug("i:%d\n",i);
		for(j=1;j<=n;j++) {
			if(chk[j]||vis[j]) continue;
			v.clear();
			vc++;
			f1=f2=0;
			dfs(j);
			if(f1) {
				go(i,f1,f2);
				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")
 
indcyc.cpp: In function 'void dfs(int)':
indcyc.cpp:38:19: warning: statement has no effect [-Wunused-value]
  debug("u:%d\n",u);
                   ^
indcyc.cpp:40:22: warning: statement has no effect [-Wunused-value]
   debug("**u:%d\n",u);
                      ^
indcyc.cpp: In function 'int main()':
indcyc.cpp:113:20: warning: statement has no effect [-Wunused-value]
   debug("i:%d\n",i);
                    ^

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