oj.uz

Submission #86705

# Submission time Handle Problem Language Result Execution time Memory
86705 2018-11-27T06:53:28 Z I_use_Brute_force Potemkin cycle (CEOI15_indcyc) C++14
20 / 100
 30 ms 5200 KB 
 #include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define pii pair <int, int>
#define sz(a) (int)(a.size()) 
#define resize(v) v.resize(unique(all(v)) - v.begin()); 
#define all(a) a.begin(), a.end()
#define forit(it, s) for(__typeof(s.begin()) it = s.begin(); it != s.end(); it ++)

using namespace std;

void Fast_Read_Out()
{
	ios_base::sync_with_stdio(0);
	cin.tie(), cout.tie();
}

void Random()
{
	unsigned int seed;
	asm("rdtsc" : "=A" (seed));
	srand(seed);        
}

unsigned int Time()
{
	 unsigned int time = clock() / 1000.00;
	 return time;
}

const int inf = int(1e9) + 123;
const int N = int(1e3) + 123;

int st;
int d[1001][1001], sor[1001], ok = 1, a[1001], dd[1001];
vector <int> res, g[N];

bool Check()
{
	res.pb(res[0]);
	for(int i = 0; i < sz(res) - 1; i++)
	{                           
		if(d[res[i]][res[i + 1]]) continue;
		else return 0;
	}
	for(int i = 0; i < sz(res); i++) dd[res[i]]++;
	for(int i = 0; i < sz(res) - 1; i++)
	{
		for(int j = 0; j < sz(g[res[i]]); j++) if(dd[g[res[i]][j]] && j != res[i + 1]) return 0;
	}
	return 1;
}

int main ()
{
	#ifdef JUDGE
		freopen("input.txt", "r", stdin);
	#endif 
	Random();
	Fast_Read_Out();
	int n, m;
	cin >> n >> m;
	for(int i = 1; i <= m; i++)
	{
		int a, b;
		cin >> a >> b;
		d[a][b]++;
		d[b][a]++;
		g[a].pb(b);
		g[b].pb(a);
	}
	for(int i = 1; i <= n; i++) sor[i] = i;
	do
	{
		int j = 1;
		for(int len = 4; len <= n;)
		{
			int j1 = j;
			while(j1 <= j + len && j1 <= n)
			{
				res.pb(sor[j1]);
				j1++;
			}
			if(Check())
			{	
				for(int i = 0; i < sz(res) - 1; i++)
				{
					cout << res[i] << ' ';
				}
				return 0;
			}
			else res.clear();
			if(j + len == n) len++;
			else j++;
		}
	}while(next_permutation(a + 1, a + n + 1));
	cout << "no" << endl;             
	#ifdef JUDGE
//		cout << Time() << endl;
	#endif
}
// Easy Peasy Lemon Squeezy                                                            Sometimes it's the very people who no one imagines anything of who do the things no one can imagine.

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Too short sequence
2 Incorrect 2 ms 508 KB Unexpected end of file - token expected
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 508 KB Too short sequence

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 508 KB Too short sequence
2 Incorrect 2 ms 532 KB Unexpected end of file - token expected

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 916 KB Too short sequence

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 936 KB Too short sequence
2 Incorrect 2 ms 936 KB Unexpected end of file - token expected

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1712 KB Unexpected end of file - token expected
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1712 KB Too short sequence
2 Incorrect 3 ms 1844 KB Unexpected end of file - token expected

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 5060 KB Too short sequence
2 Correct 10 ms 5060 KB Too short sequence
3 Incorrect 17 ms 5200 KB Unexpected end of file - token expected
4 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 5200 KB Too short sequence
2 Incorrect 10 ms 5200 KB Unexpected end of file - token expected

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 5200 KB Too short sequence
2 Incorrect 30 ms 5200 KB Unexpected end of file - token expected
3 Halted 0 ms 0 KB -