oj.uz

Submission #34350

# Submission time Handle Problem Language Result Execution time Memory
34350 2017-11-10T16:00:15 Z bnahmad15 Potemkin cycle (CEOI15_indcyc) C++14
30 / 100
 1000 ms 3940 KB 
#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

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

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3016 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 3016 KB Output is correct
2 Correct 263 ms 3016 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 3016 KB Execution timed out

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 3016 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 3016 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 3016 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 3544 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 3280 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 3940 KB Execution timed out
2 Halted 0 ms 0 KB -