oj.uz

Submission #204532

# Submission time Handle Problem Language Result Execution time Memory
204532 2020-02-26T09:01:01 Z junodeveloper Potemkin cycle (CEOI15_indcyc) C++14
70 / 100
 1000 ms 10104 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 grp[1010],gc,vis[1010],vc,st,found;
int cnt[1010];
bool chk[1010];
set<int> adj[1010];
void dfs(int u) {
	if(found)return;
	vis[u]=vc;
	if(u!=st&&chk[u]) {
		if(adj[st].count(u)) return;
		found=u;
		return;
	}
	for(auto& it:adj[u])if(vis[it]!=vc&&!(chk[u]&&chk[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,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;
		for(auto& it:adj[i])chk[it]=true;
		for(auto& it:adj[i]) {
			vc++;st=it;
			dfs(it);
			if(found) {
				go(i,it,found);
				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")
 
indcyc.cpp: In function 'int main()':
indcyc.cpp:91:8: warning: unused variable 'j' [-Wunused-variable]
  int i,j,u,v;
        ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 248 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 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 6 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 6 ms 376 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 632 KB Output is correct
2 Correct 6 ms 632 KB Output is correct
3 Correct 22 ms 1016 KB Output is correct
4 Correct 77 ms 1016 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 632 KB Output is correct
2 Correct 55 ms 632 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 598 ms 5240 KB Output is correct
2 Correct 129 ms 2424 KB Output is correct
3 Execution timed out 1075 ms 5624 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 2424 KB Output is correct
2 Execution timed out 1067 ms 2552 KB Time limit exceeded

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 494 ms 10100 KB Output is correct
2 Execution timed out 1092 ms 10104 KB Time limit exceeded
3 Halted 0 ms 0 KB -