Submission #34350

#	Time	Username	Problem	Language	Result	Execution time	Memory
34350		bnahmad15	Potemkin cycle (CEOI15_indcyc)	C++14	30 / 100	1000 ms	3940 KiB

indcyc

#include <bits/stdc++.h>
using namespace std;

int n,m,u,v;
bool cant[1001]={false},is[1001][1001]={false};
vector<int> adj[1001];
vector <int> taken;

bool check(){
	for (int i =1 ;i<taken.size();i++){
		if (!is[taken[i]][taken[i-1]])
			return false;
	}
	if (!is[taken[0]][taken.back()])
		return false;
	for (int i = 0 ;i<taken.size();i++){
		for (int j = i+2;j<taken.size();j++){
			if (i==0 && j==taken.size()-1)
				continue;
			if (is[taken[i]][taken[j]])
				return false;
		}
	}
	return true;
}
void output(vector <int> &to){
	for(auto i : to)
		printf("%d ",i+1);
	exit(0);
}
void rec(int id){
	if (id >= 4 &&check())
		output(taken);
	if (id == n)
		return;
	for(int i = 0;i<n;i++){
		if (cant[i])
			continue;
		cant[i]=true;
		taken.push_back(i);
		rec(id+1);
		cant[i]=false;
		taken.pop_back();
	}
}
int main(){
	scanf ("%d%d",&n,&m);
	for (int i = 0; i <m ;i++){
		scanf("%d%d",&u,&v);
		u--;
		v--;
		adj[u].push_back(v);
		adj[v].push_back(u);
		is[u][v]=is[v][u]=true;
	}
	rec(0);
	puts("no");
	return 0;
}

Compilation message (stderr)

indcyc.cpp: In function 'bool check()':
indcyc.cpp:10:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i =1 ;i<taken.size();i++){
                  ^
indcyc.cpp:16:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0 ;i<taken.size();i++){
                   ^
indcyc.cpp:17:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = i+2;j<taken.size();j++){
                     ^
indcyc.cpp:18:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (i==0 && j==taken.size()-1)
                 ^
indcyc.cpp: In function 'int main()':
indcyc.cpp:47:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d%d",&n,&m);
                      ^
indcyc.cpp:49:22: 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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 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