Submission #113041

#	Time	Username	Problem	Language	Result	Execution time	Memory
113041		Mahdi_Jfri	Potemkin cycle (CEOI15_indcyc)	C++14	0 / 100	25 ms	1920 KiB

indcyc

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

#define ll long long
#define pb push_back
#define hash Hash

const int maxn = 1e3 + 20;
const int base = 4001;
const int mod = 1e9 + 7;

bool visited[maxn] , A[maxn][maxn];

int pw[maxn] , d[maxn] , deg[maxn] , hash[maxn] , p[maxn];

vector<int> adj[maxn];

inline void mkay(int &a)
{
	if(a >= mod)
		a -= mod;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	pw[0] = 1;
	for(int i = 1; i < maxn; i++)
		pw[i] = 1LL * pw[i - 1] * base % mod;

	int n , m;
	cin >> n >> m;

	for(int i = 0; i < m; i++)
	{
		int a , b;
		cin >> a >> b;
		a-- , b--;

		adj[a].pb(b);
		adj[b].pb(a);

		A[a][b] = A[b][a] = 1;
	}

	for(int src = 0; src < n; src++)
	{
		queue<int> q;

		memset(visited , 0 , sizeof visited);
		memset(d , 63 , sizeof d);
		q.push(src);
		d[src] = 0;

		while(!q.empty())
		{
			int v = q.front();
			q.pop();

			for(auto u : adj[v])
				if(!visited[u])
					visited[u] = 1 , d[u] = d[v] + 1 , p[u] = v , q.push(u);
		}

		for(int v = 0; v < n; v++)
			if(visited[v] && d[v] == 3)
				return cout << v + 1 << " " << p[v] + 1 << " " << p[p[v]] + 1 << " " << src + 1 << endl , 0;
		
		for(int v = 0; v < n; v++)
			if(visited[v] && d[v] == 2)
			{
				deg[v] = hash[v] = 0;
				for(auto u : adj[v])
					if(d[u] == 1)
						deg[v]++ , mkay(hash[v] += pw[u]);
			}

		for(int v = 0; v < n; v++)
			if(visited[v] && d[v] == 2)
				for(auto u : adj[v])
					if(d[u] == 2 && (deg[v] != deg[u] || hash[v] != hash[u]))
						for(int w = 0; w < n; w++)
							if(A[src][w] && A[w][v] && !A[w][u])
								return cout << src + 1 << " " << w + 1 << " " << v + 1 << " " << u + 1 << endl , 0;
	}

	cout << "no" << endl;
}

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