oj.uz

Submission #205641

# Submission time Handle Problem Language Result Execution time Memory
205641 2020-02-29T11:13:15 Z junodeveloper Potemkin cycle (CEOI15_indcyc) C++14
100 / 100
 836 ms 10620 KB 
#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 f1,f2;
int vis[1010],vc;
bool chk[1010];
set<int> adj[1010];
bool am[1010][1010];
vi v;
void dfs(int u) {
	if(f1) return;
	vis[u]=vc;
	if(chk[u]) {
		for(auto& it:v) {
			if(!am[it][u]) {
				f1=u,f2=it;
				return;
			}
		}
		v.pb(u);
		return;
	}
	for(auto& it:adj[u])if(vis[it]!=vc)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);
		for(j=i+1;j<=n;j++) {
			if(chk[j]||vis[j]) continue;
			v.clear();vc++;
			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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 6 ms 504 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1144 KB Output is correct
2 Correct 6 ms 1016 KB Output is correct
3 Correct 8 ms 1272 KB Output is correct
4 Correct 21 ms 1272 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1016 KB Output is correct
2 Correct 14 ms 1016 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 6264 KB Output is correct
2 Correct 21 ms 3448 KB Output is correct
3 Correct 666 ms 6264 KB Output is correct
4 Correct 234 ms 3452 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3320 KB Output is correct
2 Correct 208 ms 3704 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 10616 KB Output is correct
2 Correct 86 ms 10620 KB Output is correct
3 Correct 123 ms 8056 KB Output is correct
4 Correct 836 ms 8056 KB Output is correct