Submission #1111170

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111170		Ghulam_Junaid	Potemkin cycle (CEOI15_indcyc)	C++17	10 / 100	35 ms	1924 KiB

indcyc

#include <bits/stdc++.h>
using namespace std;
 
const int N = 1e3 + 10;
const int M = 1e5 + 10;
 
int n, m;
vector<int> g[N];
bool edge[N], done;
 
int main()
{
	cin >> n >> m;
 
	for (int i=0; i<m; i++){
		int u, v;
		cin >> u >> v;
 
		g[u].push_back(v);
		g[v].push_back(u);
 
		if (v > u)
			swap(u, v);
		if (v+1 == u)
			edge[v] = 1;
	}
 
	for (int i=1; i<=n; i++)
		sort(g[i].begin(), g[i].end());
 
	// there are no other roads between those nodes...
	for (int s = 1; s <= n;){
		for (int v = s; v <= n; v++){
			if (edge[v]){
				auto lb = upper_bound(g[v+1].begin(), g[v+1].end(), v) - g[v+1].begin();
				lb--;
				if (lb == 0)
					continue;
 
				lb--;
				if (g[v+1][lb] < s)
					continue;
 
				if (((v+1) - g[v+1][lb]) == 2){
					s = v;
					break;
				}
				else{
					for (int u = g[v+1][lb]; u <= (v+1); u++)
						cout << u << " ";
					cout << endl;
					done = 1;
					s = n+1;
					break;
				}
			}
			else{
				s = v + 1;
				break;
			}
		}
	}
 
	if (!done)
		cout << "no" << endl;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 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