oj.uz

Submission #204516

# Submission time Handle Problem Language Result Execution time Memory
204516 2020-02-26T08:08:04 Z junodeveloper Potemkin cycle (CEOI15_indcyc) C++14
30 / 100
 1000 ms 526664 KB 
#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;
int cnt[1010];
bool chk[1010];
vi adj[1010];
void dfs(int u) {
	grp[u]=gc;
	for(auto& it:adj[u])if(!grp[it]&&(!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||(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)ans.pb(e),e=par[e];
	ans.pb(b);ans.pb(a);
	for(auto& it:ans)printf("%d ",it);
}
int main() {
	int i,j;
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++) {
		int u,v;
		scanf("%d%d",&u,&v);
		adj[u].pb(v);
		adj[v].pb(u);
	}
	for(i=1;i<=n;i++) {
		mset(grp,0);gc=0;
		chk[i]=true;
		for(auto& it:adj[i])chk[it]=true;
		for(auto& it:adj[i])if(!grp[it]) {
			gc++;
			dfs(it);
		}
		for(j=1;j<=gc;j++)cnt[j]=0;
		for(auto& it:adj[i])cnt[grp[it]]++;
		for(auto& it:adj[i]){
			int c=0;
			for(auto& jt:adj[it]) {
				if(chk[jt]&&grp[it]==grp[jt])c++;
			}
			if(c!=cnt[grp[it]]-1) {
				go(i,it);
				return 0;
			}
		}
		chk[i]=false;
		for(auto& it:adj[i])chk[it]=false;
	}
	puts("no");
	return 0;
}

Compilation message

indcyc.cpp: In function 'int main()':
indcyc.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~
indcyc.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&u,&v);
   ~~~~~^~~~~~~~~~~~~~

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 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 5 ms 376 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Execution timed out 1122 ms 525772 KB Time limit exceeded

Subtask #4
10.0 / 10.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Execution timed out 1114 ms 525984 KB Time limit exceeded

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Execution timed out 1120 ms 525932 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1127 ms 525900 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1123 ms 526468 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1121 ms 526168 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 1272 KB Output is correct
2 Correct 260 ms 1272 KB Output is correct
3 Execution timed out 1124 ms 526664 KB Time limit exceeded
4 Halted 0 ms 0 KB -